Комбинаторика

Основные понятия и формулы

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

Формула перестановки

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

Формула размещений

Сочетанием из по называется некое подмножество из элементов некоторого множества из .

Формула сочетаний

Свойства сочетаний:

1.

2.

3.

4.

Перестановки с повторением, если среди n элементов есть одинаковые, и если среди них - первого типа, - другого типа и т. д., то получаем формулу для перестановок с повторением.

Формула перестановки с повторением

Размещение с повторением – это упорядоченное подмножество, дге элементы не обязательно должны быть разными.

Формула размещение с повторением: .

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

Формула сочетания с повторением:

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

Решение.

Первая цифра в трехзначном числе может быть выбрана 4 способами (0 не выбирается), другая цифра 5 способами, третья тоже 5 способами. По правилу произведения все три цифры можно выбрать

Пример 2. Сколькими способами 7 человек могут встать в очередь в кассу?

Решение.

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

Пример 3. Сколькими способами можно из 7 человек выбрать комиссию из 3 человек?

Решение.

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

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

Решение.

В слове «математика» - 10 букв, из них буква «м» повторяется 2 раза, «а» - 3 раза, «т» - 2 раза. Тогда используя формулу перестановок с повторением получим ответ:

Пример 5.Автомобильный номер состоит из двух букв и 4 цифр. Какое число номеров можно составить, если буквы выбирают из 33 букв украинского алфавита?

Решение.

Найдем отдельно комбинации для букв и отдельно для чисел.

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

Для цифр: Тогда

Пример 6.Сколькими способами можно выбрать 6 одинаковых или разных пироженных в кондитерской, где есть 11 разных сортов пироженных?

Решение.

Используем сочетания с повторениями: