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

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

Правило умножения. Пусть из некоторого конечного множества 1-й объект можно выбрать способами, 2-й объект – способами, …, й объект – способами, тогда произвольный набор, перечисленных объектов, из данного множества можно выбрать способами.

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

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

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

Число всех размещений из элементов по определяется по формуле:

.

Напомним, что , при этом по определению полагают .

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

Число всех сочетаний из элементов по определяется по формуле:

.

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

Число всех перестановок из элементов множества определяется по формуле:

Пример 2.1. Пусть из пункта А в пункт В имеется 5 дорог, а из пункта В в пункт С – 6 дорог. 1) Сколько существует различных вариантов проезда из пункта А в пункт С? 2) Сколько существует различных вариантов проезда из пункта А в пункт В и обратно? 3) Сколько существует различных вариантов проезда из пункта А в пункт В и обратно при условии, что дороги туда и обратно будут разными?

Решение. 1) Существует 5 различных путей из пункта А в пункт В – это 5 способов 1-го действия, при этом существует 6 различных путей из пунктов В в пункт С – это 6 различных способов 2-го действия. Согласно правилу умножения, число различных способов выбора пути из пункта А в пункт С равно .

2) Из пункта А в пункт В ведет 5 дорог, значит, имеется 5 способов проезда туда и 5 способов проезда обратно. По правилу умножения число всех способов проезда туда и обратно равно .

3) Рассуждаем аналогично пункту 2), но учитываем, что дороги туда и обратно не совпадают, получаем, число различных способов проезда туда и обратно равно .

Пример 2.2. Сколько существует трехзначных чисел с разными цифрами?

Решение. При составлении трехзначного числа можем использовать цифры 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. На первом месте может стоять любая их девяти цифр кроме нуля. На втором месте – любая из оставшихся девяти цифр, кроме выбранной, на третьем месте – любая из оставшихся восьми цифр. Тогда по правилу умножения: трехзначных чисел имеют разные цифры.

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

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

Пример 2.4. Из группы в 25 человек нужно выделить 3 человека на дежурство. Сколькими различными способами это можно сделать?

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

.

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

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

.

Пример 2.6. Сколько существует способов расстановки 10 книг на полке?

Решение. Общее число способов расстановки определяется как число перестановок из 10 элементов и равно .

Пример 2.7. В коробке 10 деталей, из которых 6 бракованных. Найти число различных способов взятия 5 деталей, среди которых ровно 3 бракованных?

Решение. Чтобы получить множество из 5 деталей, среди которых 3 бракованные, надо совершить два действия: 1-е – взять 3 бракованных изделия – это можно сделать способами; 2-е действие – взять 2 доброкачественные детали, это можно сделать способами. Тогда по правилу умножения оба действия одновременно можно сделать способами.