Элементы комбинаторики

Элементы комбинаторики

Автор: Софронова Наталия Андреевна,

учитель математики МОУ «Упшинская ООШ»

Оршанского района Республики Марий Эл

К учебнику Ю.А.Макарычева Алгебра 9 (§ 11)

Что такое комбинаторика?

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

• Такие задачи получили название комбинаторных задач , а раздел математики , в которой рассматриваются подобные задачи называют комбинаторикой.

• Слово «комбинаторика» происходит от латинского слова combinare , что означает «соединять», «сочетать»

Примеры комбинаторных задач

• Пример 1.

Из группы теннисистов, в которую входят 4 человека – Антонов, Григорьев, Сергеев и Федоров, тренер выделяет двоих для участия в соревнованиях пар. Сколько существует вариантов выбора такой пары.

• Решение ( способ перебора возможных вариантов )

• Составим пары, в которые входит Антонов (для краткости будем писать только первые буквы фамилий): АГ, АС, АФ
• Выпишем пары, в которые входит Григорьев, но не входит Антонов: ГС, ГФ.
• Далее составим пары, в которые входит Сергеев, но не входят Антонов и Григорьев: СФ.
• Других вариантов составления пар нет.
• Получили 6 пар - АГ, АС, АФ, ГС, ГФ, СФ.
• Значит существует 6 вариантов выбора тренером пары теннисистов из данной группы.

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

• Решение с помощью схемы – дерево возможных вариантов

• Из цифр 1, 3, 5, 7 можно составить 24 трехзначных числа, в записи которых цифры не повторяются

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

• Комбинаторное правило умножения

• Ответ на вопрос примера 2 можно получить, не выписывая сами числа.

• Первую цифру можно выбрать четырьмя способами.
• Так как после выбора первой цифры останутся три, то вторую цифру можно выбрать тремя способами.
• Третью цифру можно выбрать из оставшихся двух двумя способами
• Следовательно, общее число искомых трехзначных чисел равно 4 ∙ 3 ∙ 2 = 24

Комбинаторное правило умножения

• Пусть имеется n элементов и требуется выбрать из них один за другим k элементов. Если первый элемент можно выбрать n 1 способами, после чего второй элемент можно выбрать n 2 способами из оставшихся, затем третий элемент можно выбрать n 3 способами из оставшихся и т.д., то число способов, которыми могут быть выбраны все k элементов, равно произведению n 1 ∙ n 2 ∙ n 3 ∙ … ∙ n k

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

• Решение
• Выбор первой цифры – 3 способа
• Выбор второй цифры из оставшихся трех – 3 способа
• Выбор третьей цифры из оставшихся двух – 2 способа
• Всего способов 3 ∙ 3 ∙2 = 18
• Ответ: 18 чисел

Комбинаторное правило умножения

• Сколько трехзначных чисел можно составить из цифр 0, 2, 4, 6 ?

• Решение
• Выбор первой цифры – 3 способа
• Выбор второй цифры из оставшихся трех – 4 способа
• Выбор третьей цифры из оставшихся двух – 4 способа
• Всего 3 ∙ 4 ∙ 4 = 48 способов
• Ответ: Из цифр 0,2,4,6 можно составить 48 различных трехзначных чисел.

Комбинаторное правило умножения

• Из города А в город В ведут две дороги, из города В в город С – три дороги, из города С до пристани – две дороги. Туристы хотят проехать из города А через города В и С к пристани. Сколькими способами они могут выбрать маршрут?
• Из А в В – 2 способа
• Из В в С - 3 способа
• Из С к пристани – 2 способа
• Всего способов 2 ∙ 3 ∙ 2 = 12
• Ответ: Туристы могут выбрать маршрут 12 способами.

Комбинаторное правило умножения

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

• Для удобства будем считать , что семья (бабушка, дедушка, мама, папа, дочь, сын) будет рассаживаться поочередно.
• У бабушки – 6 вариантов выбора стульев.
• У дедушки – 5 вариантов выбора стульев.
• У мамы – 4 варианта выбора стульев.
• У папы – 3 варианта выбора стульев.
• У дочери – 2 варианта выбора стульев.
• У сына – 1 вариант выбора стульев.
• По правилу умножения: 6 × 5 × 4 × 3 × 2 × 1 = 720 (дней).
• Ответ: 720 дней.

Комбинаторное правило умножения

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

Решение:

Пусть воры разбегаются поочередно.

У первого – 4 варианта выбора

У второго – 3 варианта выбора

У третьего – 2 варианта выбора

У четвертого – 1 вариант выбора

По правилу умножения

4 ∙ 3 ∙ 2 ∙ 1 = 4! = 24

Ответ: 24 способа .

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

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

Перестановкой из n элементов называется каждое расположение этих элементов в определенном порядке

Число перестановок из n элементов обозначают символом Р n ( читается Р из n)

Перестановки : формула

В рассмотренном примере мы установили, что Р 3 = 6

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

Будем рассуждать так:

На первое место можно поставить любой из трех элементов А, В, С (число способов равно 3)

На второе место можно поставить любой из двух оставшихся элементов (число способов равно 2)

На третье место можно поставить последний оставшийся элемент (число способов равно 1)

Значит число перестановок из трех элементов равно 3 ∙ 2 ∙ 1 = 6

Найдем число перестановок из n элементов

На первое место можно поставить любой из n элементов (число способов равно n )

На второе место можно поставить любой из (n -1 ) оставшихся элементов (число способов n - 1 )

На третье место можно поставить любой из (n - 2 ) оставшихся элементов (число способов n - 2)

На последнее место можно поставить последний оставшийся элемент (число способов 1 )

Значит число перестановок из n элементов равно

n ∙ (n – 1) ∙ (n - 2) ∙ … ∙ 1 = 1 ∙ 2 ∙ … ∙ (n - 2) ∙ (n - 1) ∙ n = n!

Формула Р n = n!

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

Пример 1 .

Сколькими способами можно расставить 8 участниц финального забега на восьми беговых дорожках?

Решение

Число способов равно числу перестановок из 8 элементов.

Р 8 = 8! = 1 ∙ 2 ∙ 3 ∙ 4 ∙ 5 ∙ 6 ∙ 7 ∙ 8 = 40320

Пример 2.

Сколько различных четырехзначных чисел, в которых цифры не повторяются, можно составить из цифр 0, 2, 4, 6?

Решение.

Из цифр 0, 2, 4, 6 можно получить Р 4 перестановки. Из них надо исключить те перестановки, которые начинаются с 0, так как натуральное число не может начинаться с цифры 0. Число таких перестановок Р 3 .

Искомое число четырехзначных чисел равно Р 4 – Р 3 = 4! – 3! = 24 – 6 = 18

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

Пример 3 .

Имеется 9 различных книг, четыре из которых – учебники. Сколькими способами можно расставить эти книги на полке так, чтобы все учебники стояли рядом ?

Решение.

Сначала будем рассматривать все учебники как одну книгу. Тогда на полке надо расставить не 9 книг, а 6 книг. Это можно сделать Р 6 способами.

В каждой полученной комбинации из 4 учебников можно выполнить еще Р 4 перестановок.

Значит искомое число способов расположения книг на полке равно произведению Р 6 ∙ Р 4

Р 6 ∙ Р 4 = 6! ∙ 4! = 720 ∙ 24 = 1728

Размещения

• Пусть имеется 4 шара и 3 пустых ячейки.
• Обозначим шары буквами a, b, c, d .
• В каждую ячейку можно положить по одному шару из этого набора
• Если мы поместим в первую ячейку шар а , во вторую – шар b , в третью – шар с, то получим одну из возможных упорядоченных троек шаров:
• Возможны следующие упорядоченные тройки:
• Каждую упорядоченную тройку, которую можно составить из четырех элементов, называют размещением из четырех элементов по три.

• Число размещений из n элементов по k обозначают

a

b

c

d

b

c

a

a

d

Размещением из n элементов по k (k ≤ n) называется любое множество, состоящее из k элементов, взятых в определенном порядке из данных n элементов.

Размещения

• Пусть имеется 4 шара и 3 пустых ячейки.
• Обозначим шары буквами a, b, c, d .
• Составим из элементов a, b, c, d все размещения по три элемента. Выпишем сначала размещения, которые начинаются с элемента а, затем те, которые начинаются с элемента b , с элемента с , с элемента d .

• a bc, a bd, a cb, a cd, a db, a dc,

• b ac, b ad, b ca, b cd, b da, b dc

• c ab, c ad, c ba, c bd, c da, c db

• d ab, d ac, d ba, d bc, d ca, d cb

Число размещений из 4 элементов по 3 равно 24

Размещения: формула

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

• Первый элемент можно выбрать четырьмя способами , так как им может быть любой из четырех элементов.

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

Размещения: формула

• С помощью тех же рассуждений можно подсчитать число размещений из n элементов по k можно

• Первый элемент можно выбрать n способами , так как им может быть любой из n элементов.

• Для каждого выбранного первого элемента можно (n-1) способами выбрать из (n-1) оставшихся второй элемент.
• Д ля кажд ого выбора первых двух элементов можно (n - 2) способами из (n - 2) оставшихся выбрать третий элемент и т.д.
• Наконец, для кажд ого выбора первых k-1 элементов можно n – (k-1) способами из n – (k-1) оставшихся выбрать k- й элемент
• В результате получаем

Пример 1 Учащиеся 2 класса изучают 9 предметов. Сколькими способами можно составить расписание на один день, чтобы в нем было 4 различных предметов? Решение Первый предмет можно выбрать 9 способами Второй предмет можно выбрать 8 способами из оставшихся 8 предметов Третий предмет можно выбрать 7 способами из7 оставшихся предметов. Четвертый предмет можно выбрать 6 способами из 6 оставшихся предметов Всего способов

Пример 1 Учащиеся 2 класса изучают 9 предметов. Сколькими способами можно составить расписание на один день, чтобы в нем было 4 различных предметов? Решение Любое расписание на один день, составленное из 4 различных предметов, отличается от другого набором предметов, либо порядком их следования. Значит, в этом примере речь идет о размещении из 9 элементов по 4. Имеем

Пример 2 Сколько трехзначных чисел (без повторения цифр в записи числа) можно составить из цифр 0,1,2,3,4,5,6 ? Решение Если среди семи цифр нет нуля, то число трехзначных чисел (без повторения цифр), которые можно составить из этих цифр, равно числу размещений из 7 элементов по 3. Однако среди данных цифр есть цифра 0, с которой не может начинаться трехзначное число. Поэтому из размещений из 7 элементов по 3 надо исключить те, у которых первым элементом является цифра 0. Их число равно числу размещений из 6 элементов по 2.

Сочетания

• Пусть имеются пять гвоздик разного цвета. Обозначим их буквами a, b, c, d, e . Требуется составить букет из трех гвоздик.
• Выясним, какие букеты могут быть составлены.
• Если в букет входит гвоздика а, то можно составить такие букеты:

• a b c , a b d , a b e , a c d , a c e , a d e

• Если в букет не входит гвоздика а, но входит гвоздика b, то можно составить такие букеты:

• b c d , b c e , b d e

• Если в букет не входит ни гвоздика а, ни гвоздика b, то возможен только один вариант составления букета : с d e
• Мы указали все возможные способы составления букетов, в которых по разному сочетаются три гвоздики из данных пяти. Говорят. Что мы составили все возможные сочетания из 5 элементов по 3.

Определение:

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

Число сочетаний из n элементов по k обозначают

( читается C из n по k )

Сочетания

• В рассмотренном примере
• Выведем формулу числа сочетаний из 5 элементов по 3
• Число букетов из 5 элементов по три равно
• Каждое сочетание из трех элементов (букетов) в числе размещений
• учтено 6 раз (количество перестановок из 3 элементов Р 3 = 3! = 6)
• С учетом сказанного получим:

• Аналогично , число сочетаний из n элементов по k равно

Пример 1. Из набора, состоящего из 15 красок надо выбрать 3 краски для окрашивания шкатулки. Сколькими способами можно сделать этот выбор?

Решение

Каждый выбор трех красок отличается от другого хотя бы одной краской. Значит речь идет о сочетании из 15 элементов по 3.

Пример 2. В классе учатся 12 мальчиков и 10 девочек. Для уборки территории около школы требуется выделить трех мальчиков м двух девочек. Сколькими способами это можно сделать ?

Решение