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

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

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

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

,

где (п! – читается «эн факториал»).

Пример 1. Сколькими способами можно рассадить трех гостей на три места?

Решение. Обозначим гостей А, В, С. Тогда возможными способами рассадить гостей будут перестановки из трех элементов:

1) АВС, 3) ВСА, 5) САВ,

2) АСВ, 4) ВАС, 6) СВА,

то есть количество комбинаций равно 6. Этот же результат можно получить сразу по формуле:

.

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

.

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

Решение. Обозначим претендентов А, В, С, D. Тогда возможными комбинациями будут АВ, АС, АD, ВС, ВD, СD – то есть 6 комбинаций. Этот же результат получаем по формуле:

.

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

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

.

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

Решение. Из данных цифр 1, 2, 3, 4 можно составить следующие двузначные числа: 12, 21, 13, 31, 14, 41, 23, 32, 24, 42, 34, 43. Получается 12 чисел. Эти числа отличаются либо составом (например, 12 и 13), либо порядком (12 и 21), то есть являются размещениями, поэтому сразу результат можно найти по формуле:

.

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

Пример 4. Монета подбрасывается 2 раза. Сколькими способами возможно выпадение герба и решки?

Решение. Обозначим Г – выпал герб, Р – выпала решка. Возможны следующие исходы двух подбрасываний монеты: ГГ, РР, ГР, РГ – то есть 4 способа (полученные комбинации не являются ни перестановками, ни размещениями, ни сочетаниями).

Пример 5. Вычислить значение выражения .

Решение.

.

Пример 6. Вычислить значение выражения .

Решение.