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

Комбинаторика — раздел математики, посвященный решению задач выбора и расположения в соответствии с заданными правилами элементов некоторого, обычно конечного, множества. Комбинаторные задачи — это задачи, в которых нужно подсчитать число всех возможных способов расположения некоторых предметов (объектов) или число всех возможных способов осуществления некоторого действия (комбинаций). Три наиболее важных типа комбинаций получили названия: размещений, сочетаний, перестановок. Для их определения рассмотрим множество, состоящее из n элементов. Из этого множества можно выбрать либо k элементов, либо все n и расположить их в определенном порядке. Любую из этих комбинаций будем называть соединением из n элементов по k или по n соответственно.

Определение 8. Перестановками из n элементов называют любую комбинацию, образованную из n элементов.

Очевидно, что перестановки отличаются одна от другой только порядком расположения в них элементов. Например, перестановками из цифр 1, 2, 3 будут

, всего шесть перестановок.

Заметим, что столько (шесть) различных трехзначных чисел можно образовать из цифр 1, 2, 3, если брать только различные цифры.

Число всех перестановок, образованных из n элементов, обозначают через P_n и вычисляют по формуле:

(29)

где (читается n-факториал), 0! = 1, 1! = 1.

В приведенном выше примере с тремя цифрами речь идет о перестановках из трех элементов, т.е. .

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

Очевидно, что размещения отличаются одно от другого либо самими элементами, либо порядком их расположения (следования).

Число всех размещений из n элементов по k обозначают через и вычисляют по формуле

(30)

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

Решение. В условии не оговорено, но подразумевается, что экзамены должны сдаваться в разные дни. В этом случае экзамены можно расставить на любые 10 дней и в любом порядке. Получающиеся при этом графики (комбинации) сдачи экзаменов будут отличаться один от другого как самими элементами (днями), так и порядком расположения элементов (экзаменов). Значит, речь идет о размещениях из 10 по 3. Число таких размещений равно

Ответ. Расписание экзаменов можно составить 720 способами.

Определение 10. Сочетаниями из n элементов по k называют комбинации (соединения), образованные из k различных элементов, взятых из n данных элементов, которые отличаются одно от другого хотя бы одним элементом.

Число всех сочетаний из n элементов по k обозначают через и вычисляют по формуле

(31)

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

Пример 22. Сколькими способами среди 10-ти сотрудников можно распределить 3 одинаковых (без обозначения мест) билета на концерт?

Решение. Выбор 3-х сотрудников из 10-ти для вручения билетов — это комбинации из 10-ти по 3. При этом комбинации могут отличаться одна от другой только составом. Значит, речь идет о сочетаниях из 10-ти по 3. Это число находим по формуле (31):

.

Замечание. Из формул (29-31) следует, что .

Для подсчета общего числа комбинаций часто используют правило умножения действий и правило сложения (принцип умножения и принцип сложения).

Принцип умножения. Пусть необходимо выполнить одно за другим два действия.

Если первое действие можно выполнить m₁ способами, после чего второе действие можно выполнить m₂ способами, то оба действия вместе могут быть выполнены

, (32)

способами.

Пример 23. Сколько двузначных чисел можно составить из 10-ти цифр: 0, 1, 2, 3, …, 9?

Решение. Составление двузначного числа представим в виде двух действий: выбор первой цифры и выбор второй цифры. Первое действие можно выполнить способами (на первое место нельзя ставить только цифру 0), а второе — способами. Тогда оба действия вместе, т.е. составление двузначного числа, можно выполнить способами.

Замечание. Понятно, что принцип умножения легко распространить на большее число действий: m = m₁  m₂  …  m_n.

Принцип сложения. Если два действия взаимно исключают одно другое, причем одно из них можно выполнить m₁ способами, а другое — m₂ способами, то какое-либо одно из них можно выполнить способами.

Пример 24 (к задачам № 332, 334, 337). В колоде 36 карт, которые тщательно перемешаны. Случайным образом извлекаются 3 карты. Найти вероятность того, что: 1) все извлеченные карты червовой масти; 2) среди извлеченных карт только две червовой масти; 3) хотя бы одна карта червовой масти.

Решение. Обозначим через событие А то, что все три извлеченные карты будут червовой масти, через В — то, что среди трех карт будут две карты червовой масти, и через Д — то, что среди трех карт будет хотя бы одна карта червовой масти. Вероятности Р(А), Р(В), Р(Д) найдем по формуле (28). Для этого подсчитаем m и n для каждого из событий, учитывая, что в колоде из 36 карт будет 9 карт червовой масти. Комбинации из трех карт будут отличаться одна от другой только составом. Поэтому речь идет о сочетаниях.

1) Для события А:

, , а .

2) Для события В: , а m найдем с помощью принципа умножения (32). Для этого выбор двух карт червовой масти будем считать первым действием. Это действие можно осуществить способами. Выбор одной карты не червовой масти (второе действие) можно осуществить способами. Тогда выбор двух карт червовой масти и одной не червовой осуществляется способами, т.е. . Тогда

.

3) Для события Д: . Для отыскания m следует применить сначала принцип умножения, а затем — сложения. По принципу умножения находим: — число способов выбора трех карт червовой масти, — число способов выбора двух карт червовой масти и одной не червовой, — число способов выбора одной карты червовой масти и двух — не червовой.

По принципу сложения находим число способов выбора трех карт, среди которых будет хотя бы одна карта червовой масти (или три, или две, или одна):

.

Тогда

Замечание. Вероятность события Д легче вычислить с помощью противоположного события (все три извлеченные карты не червовой масти).

Для этого используйте материал темы «Сложные события» и формулу (33). По этой формуле , а так как для , а , то

, .

Ответ. , , .