Какой отличительной чертой отмечены все задачи по комбинаторике ответ кратко

Обновлено: 02.07.2024

Часто в жизни возникает потребность определить количество возможных вариантов развития событий. Существует специальная математическая дисциплина, посвященная подобным вопросам. Она называется комбинаторикой.

План урока:

Комбинаторика и ее основные принципы

Очевидно, что если в конечном множестве содержится n элементов, то есть ровно n способов выбрать один из них.

Пример. В классе 15 человек. Сколькими способами учитель может назначить одного из них ответственным за чистоту доски?

Ответ. Таких способов ровно 15.

В комбинаторике существует два основных правила. Первое из них называется правилом сложения.

Несмотря на формулировку, по сути это очень простое правило.

Пример. В магазине продается 14 телевизоров Panasonic и 17 телевизоров Sony. Петя хочет купить один телевизор. Сколько у него вариантов покупки?

Решение. По правилу сложения Петя может выбрать один из 14 + 17 = 31 телевизоров.

Ответ: 31 телевизор.

Особое значение имеет второе правило, которое называют правилом умножения.

Проиллюстрируем это правило.

Решение. Тренер может составить 15•20= 300 разнополых пар из своих воспитанников.

Пример. Пете нужно купить технику для компьютера. В магазине продается 20 различных клавиатур, 25 моделей геймпадов и 30 компьютерных мышей. Купить надо по одному экземпляру каждого из этих устройств. Сколько вариантов покупки есть у него?

Правила сложения и умножения можно комбинировать.

Пример. Сколько слов не более чем из трех букв можно составить, используя алфавит, содержащий ровно 30 букв?

Решение. Очевидно, что слов из одной буквы можно составить ровно 30. Количество двухбуквенных слов равно количеству пар, которые можно составить из этих букв, то есть 30•30 = 900. Трехбуквенных слов можно составить 30•30•30 = 27000. Всего же слов длиною не более 3 букв будет

30 + 900 + 27000 = 27930

Далее мы изучим основные понятия комбинаторики – перестановки, размещения, сочетания.

Перестановки

Рассмотрим простейшую комбинаторную задачу. На полке расставляют по порядку книги. Их ставят вертикально друг за другом. Сколькими способами можно расставить на полке 2 книги? Очевидно, что двумя:

Либо синяя книжка будет первой слева, либо она будет находиться в конце полки, третьего варианта здесь нет. Здесь условно считается, что варианты, когда между книгами есть зазоры, идентичны вариантам без зазоров:

То есть нас интересует исключительно порядок, в котором стоят книги. Каждый из найденных вариантов называется перестановкой книг. Перестановкой называют любое конечное множество, для элементов которого указан порядок элементов.В комбинаторике перестановки являются одними из основных объектов изучения.

Например, если в забеге на 100 метров стартует 8 спортсменов, то они образуют множество участников забега. После финиша становится известно, кто занял 1-ое место, кто оказался вторым или третьим, а кто стал последним. Результат забега будет перестановкой, ведь он представляет собой список спортсменов с указанием их мест, то есть он определяет порядок между ними.

Вернемся к примеру с книгами. Обозначим количество возможных перестановок n элементов как Р_n. Две книжки можно расставить двумя разными способами, поэтому Р₂ = 2. Обозначим эти перестановки как АБ и БА. Сколько способов расстановки есть в случае трех книжек? Их все можно получить из вариантов с 2 книжками, добавляя между ними книгами ещё один том:

Видно, что между 2 книгами есть три позиции, на которые можно поставить 3-ий том. Общее количество вариантов равно произведению числа этих позиций и количества вариантов для 2 книг, то есть Р₃ = 3•Р₂ = 3•2 = 6:

Итак, мы имеем 6 перестановок для 3 книг:

А сколько перестановок существует для 4 книг? Снова-таки, между тремя книгами 4-ый том можно поставить четырьмя способами:

То есть из перестановки трех книг АБВ можно получить 4 перестановки:

Всего существует 6 перестановок для 3 книг (Р₃ = 6), и для каждой из них можно построить 4 перестановки из 4 книг. Получается, что общее количество перестановок 4 книг равно

Продолжая подобные рассуждения, можно убедиться, что количество перестановок 5 предметов в 5 раз больше, чем перестановок для 4 объектов:

И вообще, если число перестановок n объектов равно Р_n, то количество перестановок (n + 1)объекта равно в (n + 1)раз больше:

При этом отметим, что 1 книгу можно расставить на полке только одним способом:

То есть Р₁ = 1. Теперь выпишем значения чисел Р при разном количестве переставляемых предметов, используя формулуР_n+1 = (n + 1)Р_n

Видно, что количество перестановок n объектов равно произведению всех натуральных чисел от 1 до n. В математике есть специальная функция для вычисления значения этого произведения. Она называется факториалом и обозначается восклицательным знаком.

Например, факториал 6 вычисляется так:

Мы убедились на примере с книгами, что количество перестановок из n различных объектов, которое обозначается как Р_n, равно n!.

Относительно факториала надо заметить несколько важных моментов. Во-первых, очевидно, что факториал единицы равен 1:

Во-вторых, иногда в комбинаторных задачах приходится вычислять факториал нуля. По ряду соображений эта величина также принимается равной единице

Объяснить это можно так. Факториал числа можно представить как произведение этого числа и факториала предыдущего числа, например:

5! = 1•2•3•4•5 = (1•2•3•4)•5 = 4!•5

7! = 1•2•3•4•5•6•7 = (1•2•3•4•5•6)•7 = 6!•7

В общем случае формула выглядит так:

Из неё несложно получить, что

Подставив в эту формулу единицу, получим

Пример. Сколькими способами тренер может расставить 4 участников эстафеты 4х400 м по этапам эстафеты?

Решение. Количество таких способов равно числу перестановок 4 различных объектов Р₄:

Пример. Вася решил изучать сразу 7 иностранных языков, причем на занятия по каждому из них он собирается выделить ровно один день в неделе. Сколько вариантов расписаний занятий может составить себе Вася?

Решение. В данном случае расписание занятий – это порядок, в котором Вася в течение недели будет изучать иностранные языки, например:

Такое расписание можно описать последовательностью символов:

Ф, Ан, И, К, Я, Ар, П

Создавая расписание, Вася переставляет 7 языков, поэтому общее количество расписаний равно 7!:

Пример. Сколько пятизначных цифр можно записать, используя цифры 0, 1, 2, 3, 4, причем каждую не более одного раза?

Решение. Общее количество перестановок 5 цифр составляет Р₅. Однако нельзя начинать запись числа с нуля. Так как, перестановка 12340 – это пятизначное число (двенадцать тысяч триста сорок), а перестановка 03241 – не является пятизначным числом.

Расстановок, начинающихся с нуля, ровно Р₄, поэтому общее количество допустимых цифр равно Р₅ – Р₄:

Р₅ – Р₄ = 5! – 4! = 120 – 24 = 96

Пример. На полке расставляют 7 книг, однако 3 из них образуют трехтомник. Тома трехтомника должны стоять друг за другом и в определенном порядке. Сколько существует способов расстановки книг?

Решение. Будем считать трехтомник одной книгой. Тогда нам надо расставить 5 книг

Пример. Необходимо расставить 7 книг на полке, но три из них принадлежат одному автору. Их надо поставить друг с другом, но они могут стоять в любом порядке. Сколько возможно перестановок книг.

Решение. Снова будем считать три книги как один трехтомник. Получается, что существует 5! = 120 вариантов. Однако каждому из них соответствует 3! = 6 расстановок книг внутри трехтомника, например:

В итоге на каждую из 120 расстановок приходится 6 вариантов расстановки трехтомника, а общее число расстановок равно, согласно правилу умножения, произведению этих чисел:

Перестановки с повторениями

До этого мы рассматривали случаи, когда все переставляемые объекты были различными. Однако порою некоторые из них не отличаются друг от друга. Пусть на полке надо расставить 3 книги, но две из них одинаковые. Сколько тогда существует перестановок? Общее число перестановок 3 книг составляет 3! = 6:

1-ая группа: БАА1А2, БАА2А1, БА1АА2, БА1А2А, БА2АА1, БА2А1А

2-ая группа: АБА1А2, АБА2А1, А1БАА2, А1БА2А, А2БАА1, А2БА1А

3-ая группа: АА1БА2, АА2БА1, А1АБА2, А1А2БА, А2АБА1, А2А1БА

4-ая группа: АА1А2Б, АА2А1Б, А1АА2Б, А1А2АБ, А2АА1Б, А2А1АБ

И снова для подсчета числа оригинальных перестановок надо из общее число расстановок поделить на количество дубликатов в каждой группе:

Для обозначения перестановок с повторениями используется запись

где n – общее количество объектов, а n₁, n₂, n₃,… n_k – количество одинаковых элементов. Например, в задаче с 4 книгами мы искали величину Р₄(3, 1), потому что всего книг было 4, но они были разбиты на две группы, в одной из которых находилось 3 одинаковых тома (буквы А, А1, А2), а ещё одна книга (Б) составляла вторую группу. Мы заметили, что для вычисления числа перестановок с повторениями надо общее число перестановок делить на количество дублирующих перестановок. Формула в общем случае выглядит так:

Пример. Вася решил, что ему стоит изучать только два иностранных языка. Он решил 4 дня в неделю тратить на английский, а оставшиеся три дня – на испанский. Сколько расписаний занятий он может себе составить.

Решение. Вася должен расставить 3 урока испанского и 4 урока английского, тогда n₁ = 3, а n₂ = 4. Общее количество уроков равно 3 + 4 = 7. Тогда

Обратите внимание, что для удобства при делении факториалов мы не вычисляли их сразу, а пытались сократить множители. Так как в ответе любой комбинаторной задачи получается целое число, то весь знаменатель дроби обязательно сократится с какими-нибудь множителями в числителе.

Пример. У мамы есть 3 яблока, 2 банана и 1 апельсин. Эти фрукты она распределяет между 6 детьми. Сколькими способами она может это сделать, если каждый должен получить по фрукту?

Решение. Всего есть три группы фруктов. В первой находится 3 яблока, поэтому n₁ = 3. Во второй группе 2 банана, поэтому n₂ = 2. В третьей группе только 1 апельсин, поэтому n_k = 1. Общее число фруктов равно 6. Используем формулу:

В знаменателе формулы для перестановок с повторениями мы записываем число объектов в каждой группе одинаковых предметов. Так, если переставляются 3 яблока, 2 банана и 1 апельсин, то в знаменателе мы пишем 3!•2!•1!. Но что будет, если в каждой группе будет находиться ровно один уникальный объект? Тогда мы запишем в знаменателе произведение единиц:

В итоге мы получили ту же формулу, что и для перестановок без повторов. Другими словами, перестановки без повтора могут рассматриваться просто как частный случай перестановок с повторами.

Размещения

Пусть в футбольном турнире участвуют 6 команд. Нам предлагают угадать те команды, которые займут призовые места (то есть первые три места). Сколько вариантов таких троек существует?

Сначала запишем ту команду, которая выиграет турнир. Здесь есть шесть вариантов, по количеству участвующих команд. Запишем эти варианты:

Далее выберем один из вариантов и для него укажем серебряного призера соревнований. Здесь есть только 5 вариантов, ведь 1 из 6 команд уже записана на 1-ом месте:

В данном случае из некоторого множества команд мы выбрали несколько и расположили их в каком-то порядке. То есть мы выбрали упорядоченное множество. В комбинаторике оно называется размещением.

Если общее число команд обозначить как n (в этом примере n = 6), а количество упорядочиваемых команд равно k, то количество таких размещений в комбинаторике обозначается как

В примере с командами количество размещений равнялось 120:

Для нахождения этого числа мы перемножили k (3)множителей. Первый из них был равен n(6), так как каждая из n команд могла занять первая место. Второй множитель был равен (n– 1), так как после определения чемпиона мы могли поставить на вторую позицию одну из (n– 1) команд. Третий множитель был равен (n– 2). По этой логике каждый следующий множитель будет меньше предыдущего на единицу. Например, чтобы вычислить число размещений из 7 по 4, надо перемножить 4 множителя, первый из которых равен 7, а каждый следующий меньше на 1:

Однако математически удобнее представлять это произведение как отношение двух факториалов. Для этого умножим количество размещений на дробь 3!/3!, равную единице. Естественно, число размещений из-за умножения на единицу не меняется:

Число 3 в данном случае можно получить, если из 7 вычесть 4. В общем случае из числа n надо вычесть число k. Тогда формула для вычисления количества размещений примет вид:

Решение. Для составления расписания нужно выбрать 5 предметов и расставить их по порядку. Поэтому нам необходимо найти размещение из 12 по 5:

Пример. В вагоне 10 свободных мест. В него зашло 6 пассажиров. Сколькими способами они могут расположиться в вагоне?

Решение. Из десяти мест надо выбрать шесть и указать для каждого, какому пассажиру оно соответствует. То есть каждый вариант рассадки пассажиров – это размещение из 10 по 6. Найдем их количество:

Заметим, что перестановка – это частный случай размещения, когда k = n. Действительно, если нам надо указать тройку призеров турнира, в котором участвуют 6 команд, то мы указываем размещение из 6 по 3. Но если мы указываем для каждой из 6 команд, какое место она займет в чемпионате, то это размещение из 6 по 6. С другой стороны, это расстановка одновременно является и перестановкой 6 команд. Убедимся, что в этом частном случае формула для подсчета количества размещений покажет тот же результат, что и формула для перестановок

Для примера с 6 командами это будет выглядеть так:

Здесь мы использовали тот факт, что факториал нуля принимается равным единице. Данное рассуждение можно, наоборот, использовать для того, чтобы доказать, что факториал нуля – это единица.

Сочетания

Однако порою этот порядок не имеет значения. Так, существует известная лотерея, где предлагается угадать 7 чисел из 49, которые выпадут во время розыгрыша из барабана. При этом порядок их выпадения не играет никакой роли. Игрок, выбирая эти 7 чисел, с точки зрения математики формирует сочетание из 49 по 7.

Количество возможных сочетаний из n по k обозначается буквой С:

Для вычисления количеств сочетаний из n по k сначала найдем количество аналогичных размещений. Оно вычисляется по формуле:

Однако ясно, что, как и в случае с перестановками с повторениями, некоторые сочетания мы посчитали несколько раз. Вернемся к примеру с командами. Если мы выбрали команды Л (Локомотив) , З (Зенит) и К (Краснодар), то мы можем составить ровно 3! = 6 размещений из них:

Однако все они соответствуют только одному сочетании – ЛКЗ. Таким образом, считая количество размещений, мы посчитали каждое сочетание не один, а 3! раз. Поэтому для нахождения количества сочетаний в комбинаторике надо поделить число размещений на число перестановок k элементов:

Эта формула связывает важнейшие понятия комбинаторики – перестановки, сочетания и размещения. Подставим в неё формулы для размещений и перестановок и получим:

Пример. Сколько троек призеров турнира можно составить, выбирая три футбольные команды из шести?

Решение. Посчитаем число сочетаний из 6 по 3:

Решение. В каждом из этих случаев игрок выбирает сочетание нескольких чисел. Посчитаем их число:

Ответ: 376992; 8145060; 85900584

Пример. На плоскости отмечены 8 точек, причем никакие три из них не лежат на одной прямой. Сколько различных прямых можно провести через них? Сколько треугольников и четырехугольников можно построить с вершинами в этих точках?

Решение. Для того чтобы провести прямую, достаточно выбрать любые 2 точки из 8. Общее количество прямых будет равно числу сочетаний из 8 по 2:

Заметим принципиальную важность того условия, что никакие три точки не лежат на одной прямой. Оно гарантирует, что при выборе двух различных точек мы будем получать различные прямые. Если бы, например, точки АВС лежали бы на одной прямой, то при выборе сочетаний АВ, ВС и АС мы получали бы одну и ту же прямую:

Это же условие гарантирует, что, выбрав любые 3 и 8 точек, мы сможем построить треугольник с вершинами в этих точках, а выбрав 4 точки, получим четырехугольник. Поэтому для подсчета количества треугольников и четырехугольников следует искать число сочетаний по 3 и 4:

Ответ: 28 прямых, 56 треугольников и 70 четырехугольников.

Пример. В одной урне находится 10 различных шаров с номерами от 0 до 9, а в другой – 8 различных шаров с первыми восемью буквами алфавита. По условиям лотереи ведущий вытаскивает из первой урны два шара с числами, а из второй – три шара с буквами. Для победы в лотерее надо угадать выпавшие шары. Сколько комбинаций шаров может выпасть в игре?

Решение. Посчитаем отдельно, сколькими способами можно выбрать 2 шара с цифрами из 10 и 3 шара с буквами из 8:

По правилу умножения мы должны перемножить эти числа, чтобы найти общее количество возможных вариантов:

Заметим, что выбирая, например, сочетание из 49 по 7, мы одновременно выбираем и сочетание из 49 по 49 – 7 = 42. Действительно, игрок, обводящий в кружок в лотерейном билете свои 7 счастливых чисел, одновременно и определяет остальные 42 числа, какие числа он НЕ считает счастливыми. Для наглядности запишем число сочетаний в обоих случаях:

Получили одну и ту же дробь, в которой отличается лишь последовательность множителей в знаменателе. Можно показать, что и в общем случае число сочетаний из n по k совпадает с количеством сочетаний из n по (n– k):

Комбинаторика – раздел математики, который изучает задачи выбора и расположения элементов из некоторого основного множества в соответствии с заданными правилами. Формулы и принципы комбинаторики используются в теории вероятностей для подсчета вероятности случайных событий и, соответственно, получения законов распределения случайных величин. Это, в свою очередь, позволяет исследовать закономерности массовых случайных явлений, что является весьма важным для правильного понимания статистических закономерностей, проявляющихся в природе и технике.

Правила сложения и умножения в комбинаторике

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n₁ способами, второе действие n₂ способами, третье – n₃ способами и так до k-го действия, которое можно выполнить n_k способами, то все k действий вместе могут быть выполнены:

Пример 2.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

После того, как мы выбрали первого дежурного, второго мы можем выбрать из оставшихся 25 человек, т.е. 25-ю способами.

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

Сочетания без повторений. Сочетания с повторениями

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?

Пример 3.

Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?

Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:

Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?

Пример 4.

В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

Т.к. среди 7 пирожных могут быть пирожные одного сорта, то число способов, которыми можно купить 7 пирожных, определяется числом сочетаний с повторениями из 7 по 4.

Размещения без повторений. Размещения с повторениями

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?

Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:

Перестановки без повторений. Перестановки с повторениями

Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?

Пример 7.

Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k

Пример 8.

Свидетельство и скидка на обучение каждому участнику

Зарегистрироваться 15–17 марта 2022 г.

Ответить на вопросы

Какой раздел математики называют комбинаторикой?

Какой отличительной чертой отмечены все задачи по комбинаторике?

Составить 5 комбинаторных задач с решением, связанные с Вашей группой.

Примеры:

Девочки нашего класса дежурят в столовой. Сколькими способами можно выбрать 2-х дежурных из 5 девочек?

На первое место – можно поставить любую из пяти девочек, а на второе место – любую из 4. По правилу произведения имеем, 5·4=20, но при таком подсчёте, одна и та же пара подсчитана дважды ( пара 12 и 21). Тогда окончательный ответ, (способов),

Ответ: 10 вариантов.

Девочки нашего класса решили обменяться фотографиями. Сколько нужно сделать фотографий, учитывая, что их 5 человек?

В классе 5 девочек, каждая подарит 4 фотографии, то общее количество фотографий 5·4= 20 ( Или: важно, кто кому подарит фотографию, то имеем дело с размещением )

Ответ: 20 вариантов.

Составляя расписание на понедельник в 10 классе, завуч может поставить 6 уроков: алгебра, физика, биология, труд, история, физкультура. Сколько существует вариантов расписания?

Ответ: 720 вариантов

В классе 7 человек успешно занимаются математикой. Сколькими способами можно выбрать из них двоих для участия в математической олимпиаде?

Первым может быть любой из 7, тогда вторым любой из 6, учитывая одинаковые пары, имеем

подготовка к ЕГЭ/ОГЭ и ВПР
по всем предметам 1-11 классов

Курс повышения квалификации

Дистанционное обучение как современный формат преподавания

Курс повышения квалификации

Инструменты онлайн-обучения на примере программ Zoom, Skype, Microsoft Teams, Bandicam

Курс добавлен 31.01.2022
Сейчас обучается 30 человек из 19 регионов

Курс профессиональной переподготовки

Математика: теория и методика преподавания в образовательной организации

Сейчас обучается 683 человека из 75 регионов

Для учеников 1-11 классов и дошкольников
Бесплатные сертификаты учителям и участникам

Дистанционные курсы для педагогов

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

5 613 231 материал в базе

ЗП до 91 000 руб.
Гибкий график
Удаленная работа

Самые массовые международные дистанционные

Школьные Инфоконкурсы 2022

Свидетельство и скидка на обучение каждому участнику

Другие материалы

Вам будут интересны эти курсы:

Оставьте свой комментарий

10.05.2017 5415
DOCX 143.1 кбайт
22 скачивания
Рейтинг: 5 из 5
Оцените материал:

Настоящий материал опубликован пользователем Фазылова Елена Халиловна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

Автор материала

40%

Подготовка к ЕГЭ/ОГЭ и ВПР
Для учеников 1-11 классов

Московский институт профессиональной
переподготовки и повышения
квалификации педагогов

Дистанционные курсы
для педагогов

663 курса от 690 рублей

Выбрать курс со скидкой

Выдаём документы
установленного образца!

Учителя о ЕГЭ: секреты успешной подготовки

Время чтения: 11 минут

Рособрнадзор предложил дать возможность детям из ДНР и ЛНР поступать в вузы без сдачи ЕГЭ

Время чтения: 1 минута

Минтруд предложил упростить направление маткапитала на образование

Время чтения: 1 минута

ГИА для школьников, находящихся за рубежом, может стать дистанционным

Время чтения: 1 минута

Время чтения: 2 минуты

Отчисленные за рубежом студенты смогут бесплатно учиться в России

Время чтения: 1 минута

Новые курсы: преподавание блогинга и архитектуры, подготовка аспирантов и другие

Время чтения: 16 минут

Подарочные сертификаты

Ответственность за разрешение любых спорных моментов, касающихся самих материалов и их содержания, берут на себя пользователи, разместившие материал на сайте. Однако администрация сайта готова оказать всяческую поддержку в решении любых вопросов, связанных с работой и содержанием сайта. Если Вы заметили, что на данном сайте незаконно используются материалы, сообщите об этом администрации сайта через форму обратной связи.

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение администрации может не совпадать с точкой зрения авторов.

Комбинаторика - это наука, с который каждый встречается в повседневной жизни: сколько способов выбрать 3 дежурных для уборки класса или сколько способов составить слово из данных букв. В целом, комбинаторика позволяет вычислить, сколько различных комбинаций, согласно некоторым условиям, можно составить из заданных объектов (одинаковых или разных).

Как наука комбинаторика возникла еще в 16 веке, а теперь ее изучает каждый студент (и зачастую даже школьник). Начинают изучение с понятий перестановок, размещений, сочетаний (с повторениями или без), на эти темы вы найдете задачи и ниже. Наиболее известные правила комбинаторики - правила суммы и произведения, которые чаще всего применяются в типовых комбинаторных задачах.

Ниже вы найдете несколько примеров задач с решениями на комбинаторные понятия и правила, которые позволят разобраться с типовыми заданиями. Если есть трудности с задачами - заказывайте контрольную по комбинаторике.

Калькуляторы онлайн и примеры

Задачи по комбинаторике с решениями онлайн

Задача 1. У мамы 2 яблока и 3 груши. Каждый день в течение 5 дней подряд она выдает по одному фрукту. Сколькими способами это может быть сделано?

Задача 2. Предприятие может предоставить работу по одной специальности 4 женщинами, по другой - 6 мужчинам, по третьей - 3 работникам независимо от пола. Сколькими способами можно заполнить вакантные места, если имеются 14 претендентов: 6 женщин и 8 мужчин?

Задача 3. В пассажирском поезде 9 вагонов. Сколькими способами можно рассадить в поезде 4 человека, при условии, что все они должны ехать в различных вагонах?

Задача 4. В группе 9 человек. Сколько можно образовать разных подгрупп при условии, что в подгруппу входит не менее 2 человек?

Задача 5. Группу из 20 студентов нужно разделить на 3 бригады, причем в первую бригаду должны входить 3 человека, во вторую — 5 и в третью — 12. Сколькими способами это можно сделать.

Задача 6. Для участия в команде тренер отбирает 5 мальчиков из 10. Сколькими способами он может сформировать команду, если 2 определенных мальчика должны войти в команду?

Задача 7. В шахматном турнире принимали участие 15 шахматистов, причем каждый из них сыграл только одну партию с каждым из остальных. Сколько всего партий было сыграно в этом турнире?

Задача 8. Сколько различных дробей можно составить из чисел 3, 5, 7, 11, 13, 17 так, чтобы в каждую дробь входили 2 различных числа? Сколько среди них будет правильных дробей?

Задача 9. Сколько слов можно получить, переставляя буквы в слове Гора и Институт?

Задача 10. Каких чисел от 1 до 1 000 000 больше: тех, в записи которых встречается единица, или тех, в которых она не встречается?

Комбинаторными задачами называют такие задачи, решение которых заключается в формулировке неких комбинаций из ряда элементов, отобранных в зависимости от определенных условий, или в подсчете количества таких комбинаций.

К типичным комбинаторным задачам можно отнести следующие:

определение числа конфигураций методами комбинаторики, соответствующими конкретным правилам, к примеру, доказательство или опровержение существования подобных комбинаций;
поиск применимого на практике алгоритма для построения комбинаций;
формулировка свойств, которыми обладает какой-либо класс комбинаторных комбинаций.

В процессе решения задач по комбинаторике требуется применять разные модели конфигураций. Наглядными примерами комбинаторных конфигураций являются:

Размещение из n компонентов по k — в виде упорядоченного комплекса из k неких компонентов какого-то n-элементного множества.
Перестановка из n элементов (например, чисел 1, 2, … n) в виде какого-то упорядоченного комплекса данных компонентов. Под перестановкой, кроме прочего, понимают размещение из n элементов по n.
Сочетание из n по k является набором k компонентов, отобранных из неких n компонентов. Комплексы, которые обладают идентичным порядком следования компонентов и могут отличаться в зависимости от состава, называют одинаковыми. Данное условие выражает отличие между сочетанием и размещением.
Композиция числа n представляет собой любую запись n, как упорядоченную сумму, в состав которой включены числа больше нуля из множества целых чисел.
Разбиение числа n выражает любую запись n, как неупорядоченную сумму, состоящую из чисел больше нуля из множества целых чисел.

Приведем несколько примеров комбинаторных задач:

Найти количество методов, с помощью которых можно расположить n вещей по m полкам, чтобы удовлетворить условиям определенного ограничения.
Определить число существующих функций F из m-элементного множества в n-элементном, которые соответствуют неким ограничениям.
Найти количество разнообразных способов перестановок карт в колоде из 52 штук.
Описана ситуация игры в кости. После подбрасывания пары костей выпавшие цифры суммируются. Нужно вычислить количество комбинаций, в которых цифры на верхних гранях костей в сумме равны числу 12.

Общее понятие комбинаторики, история создания, разделы

Комбинаторика представляет собой математический раздел, в рамках которого решают задачи на выбор и расположение элементов, составляющих какое-то множество согласно неким условиям.

При работе с комбинаторными задачами используют ряд правил. С их помощью можно определить какую-то выборку из компонентов начального множества. Такая подборка носит название комбинаторной конфигурации. Наиболее простыми примерами служат:

перестановка;
сочетание;
размещение.

Комбинаторика обладает связями с разными научными математическими направлениями, в том числе такими, как алгебра, геометрия, теория вероятности, теория чисел. Принципы комбинаторики применимы в разных сферах знаний, включая генетику, информатику, статистику, статистическую физику, лингвистику.

Формулы для аппроксимации факториала, которые позволяют связать между собой принципы математического анализа и комбинаторики, были выведены Абрахамом де Муавром и Джеймсом Стирлингом. Окончательно наука в качестве отдельного раздела сформировалась в трудах Эйлера. Фундаментом для развития комбинаторики считают научные труды Паскаля, Ньютона, Якоба Бернулли и Эйлера.

С помощью исследований Дж. Дж. Сильвестра (конец XIX века) и Перси Макмэна (начало XX века) сформированы основные положения перечислительной и алгебраической комбинаторики. Большую ценность для науки представляла Теория графов.

Благодаря стремительному развитию дискретной математики, информатики, кибернетики и планирования эксперимента во второй половине ХХ века, комбинаторика пополнилась новыми идеями. С ХХ века развивалась комбинаторная геометрия, что сопровождалось доказательством теорем Радона, Хелли, Юнга, Бляшке, изопериметрической теоремы. Теория Рамсея была сформулирована в 1940-х годах.

Способы решения комбинаторных задач, схема

Комбинаторные задачи решают следующими методами:

способ перебора;
дерево вероятных вариантов;
комбинаторный принцип умножения.

Когда существуют взаимно исключающие друг друга действия А и В, и действие А допустимо реализовать m способами, а В — n способами, для выполнения одного из рассматриваемых действий предусмотрено (n + m) способов.

Рассмотрим пример. Допустим, что в состав класса входят 16 мальчиков и 10 девочек. Необходимо определить число методов для назначения одного дежурного.

Заметим, что роль дежурного может исполнять и мальчик, и девочка. Согласно правилу суммы:

Таким образом, определить дежурного можно каким-либо из 26 способов.

Правило произведения: когда необходимо выполнить k действий в определенной последовательности, при условии, что для первого действия предусмотрено n1 способов, для второго — n2 способов, для третьего — n3 способов и так до k-го действия, которое можно выполнить nk способами, то все k действий совместно можно реализовать следующим числом способов:

N = n 1 · n 2 · … · n k

Рассмотрим предыдущую задачу. Попробуем рассчитать количество способов для назначения двух дежурных.

Первого дежурного допустимо назначить одним из 26 методов. Второго дежурного получится выбрать с помощью 25 способов. Согласно теореме умножения, двух дежурных можно выбрать следующим количеством способов:

Поиск числа сочетаний без повторений является типичной задачей комбинаторики.

Сочетание с повторениями. Количество способов, с помощью которых получится отобрать m из n разных предметов:

C n m = n ! m ! ( n - m ) !

Попробуем решить следующую задачу. Представим, что нужно упаковать для подарка 4 книги из 10 имеющихся в наличии. Требуется найти число способов такого подбора.

Воспользуемся записанной ранее формулой:

C 1 0 4 = 10 ! 6 ! 4 ! = 210

Сочетание без повторений. Существует по r идентичных вещей каждого из n разных видов. Количество способов выбора m при m ≤ r из данных n · r предметов определяется следующим образом:

C ¯ n m = C n + m - 1 m = ( n + m - 1 ) ! m ! ( n - 1 ) !

Приведем пример. Допустим, что имеется 4 вида сладостей, в том числе: наполеон, эклер, песочное и слоеное пирожное. Нужно вычислить число способов покупки 7 десертов.

Воспользуемся записанной ранее формулой:

C ¯ 4 7 = C 4 + 7 - 1 7 = 10 ! 7 ! 3 ! = 120

Размещение без повторений. Количество способов выбора и размещения по m разным местам m из n неодинаковых вещей:

A n m = n ! ( n - m ) !

Разберем типичное задание. Газета содержит 12 страниц. В издании требуется напечатать 4 фотографии. Нужно определить количество способов сделать это, чтобы на одной странице была напечатана максимум одна фотография.

Применим формулу размещения без повторений:

A 1 2 4 = 12 ! ( 12 - 4 ) ! = 12 ! 8 ! = 9 · 10 · 11 · 12 = 11880

Размещение с повторениями. Количество способов подбора и размещения по m неодинаковым местам m из n предметов, среди которых встречаются идентичные, определяется по формуле:

Рассмотрим задачу. Мальчик получил печати с цифрами 1, 3 и 7. С их помощью нужно пронумеровать книги пятизначными числами, чтобы сформировать каталог. Попробуем выяснить количество разнообразных пятизначных номеров, которые можно получить в данном случае.

Воспользуемся формулой размещения с повторениями:

A ¯ 3 5 = 3 5 = 243

Перестановка без повторов. Количество способов размещения n неодинаковых вещей на n разных местах равно:

Подставим значения в формулу перестановки без повторения:

P 4 = 4 ! = 1 · 2 · 3 · 4 = 24

Перестановка с повторениями. Количество способов перестановки n предметов, которые размещены на n разных местах, при наличии k неодинаковых типов (k P n 1 , n 2 , … n k = n ! n 1 ! n 2 ! . . . n k ! .

P 9 ( 1 , 4 , 3 , 1 ) = 9 ! 1 ! · 4 ! · 3 ! · 1 ! = 2520

Упростить решение подобных задач можно, используя удобную схему, в которой указаны основные комбинаторные методы:

Примеры простейших задач с решением

Записаны разные делители для числа 12. Нужно вычислить количество выписанных чисел.

Перечислим все делители для числа 12:

Всего получается 6 чисел.

Шесть пчел опыляют два неодинаковых цветка. На один цветок садится только одна пчела. Требуется отобрать пчел для опыления данной пары цветков. Нужно найти число способов распределения пчел по двум различным цветкам.

Один цветок может опылять одна пчела из шести. После выбора одной пчелы для первого цветка претендентов на второй цветок останется всего 5. Такая ситуация возможна при выборе любой из пчел для первого цветка. Можно сделать вывод, что каждый из 6 выборов для первого цветка дает 5 разных вариантов для второго цветка. Тогда общее количество способов распределения составит:

Записаны разные делители для числа 120. Нужно определить количество выписанных чисел.

В первую очередь следует выполнить разложение числа 120 на простые множители:

Вычислим все делители числа 120:

( a 1 , b 1 , c 1 ) и ( a 2 , b 2 , c 2 )

Тогда различными являются следующие числа:

2 a 1 · 3 b 1 · 5 c 1 и 2 a 2 · 3 b 2 · 5 c 2

В результате, количество различных делителей для числа 120 соответствует числу разных троек, записанных в виде (a, b, c). При этом:

a обладает одним из четырех значений;
b имеет одно из пары значений;
c принимает одно из двух значений.

Таким образом, искомое количество составит:

На день рождения к мальчику должно прийти 6 гостей. Требуется накрыть праздничный стол. Именинник желает сидеть во главе стола. Нужно определить количество способов, с помощью которых можно рассадить гостей за столом.

По условию задачи одно место закреплено за именинником, поэтому его можно не учитывать в расчетах. Если один гость займет первый стул, то второй стул достанется кому-то из пяти оставшихся гостей. Последний стул достанется в итоге одному гостю. Вычислим количество вариантов:

6 ! = 1 · 2 · 3 · 4 · 5 · 6 = 720

Записаны неодинаковые делители для числа 2016. Нужно посчитать количество таких чисел.

В первую очередь следует выполнить разложение числа 2016 на множители:

2016 = 2 5 · 3 2 · 7

Каждый из делителей числа 2016 можно вычислить таким образом:

a имеет значения 0, 1, 2, 3, 4 или 5;
для b допускаются значения 0, 1 или 2;
c может принимать значения 0 или 1.

Предположим, что следующие тройки не совпадают:

( a 1 , b 1 , c 1 ) и ( a 2 , b 2 , c 2 )

Тогда данные числа являются различными:

2 a 1 · 3 b 1 · 7 c 1 и 2 a 2 · 3 b 2 · 7 c 2

Можно заключить, что число 2016 имеет столько неодинаковых делителей, сколько имеется разных троек в виде (a, b, c). При этом:

a имеет одно из шести значений;
b обладает одним из трех значений;
c принимает одно из двух значений.

Количество чисел составит: 6 · 3 · 2 = 36

Имеется пара чисел:

N = p 1 k 1 · … · p n k n и M = N · p i

Здесь p 1 , . . . , p n – простые числа, i – некоторое число из множества < 1 , 2 , . . . , n >. Нужно определить во сколько раз число неодинаковых делителей М больше по сравнению с количеством разных делителей N.

Вычислим делители числа N:

p 1 a 1 · … · p n a n

При этом a 1 является каким-то из k 1 + 1 значений (вероятные значения: 0 , 1 , . . . , k 1 ) , a n обладает одним из k n + 1 значений. При несовпадении упорядоченных наборов ( b 1 , … , b n ) и ( c 1 , … , c n ) являются неодинаковыми следующие числа:

p 1 b 1 · … · p n b n и p 1 c 1 · … · p n c n

В результате число N обладает различными делителями в количестве, равном числу существующих упорядоченных наборов, записанных в виде:

При этом a 1 имеет одно из k 1 + 1 значений, a n обладает одним из k n + 1 значений. В результате количество подходящих наборов составит:

( k 1 + 1 ) · … · ( k i + 1 ) · … · ( k n + 1 )

Аналогичным способом можно вычислить число неодинаковых делителей для М:

( k 1 + 1 ) · … · ( k i + 2 ) · … · ( k n + 1 )

Нужное соотношение можно записать таким образом:

( k 1 + 1 ) · … · ( k i + 2 ) · … · ( k n + 1 ) ( k 1 + 1 ) · … · ( k i + 1 ) · … · ( k n + 1 ) = k i + 2 k i + 1

Читайте также: