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

Согласно классическому определению подсчёт вероятности события сводится к подсчёту числа благоприятствующих ему исходов.

Делают это обычно комбинаторными методами.

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

Многие комбинаторные задачи можно решить с помощью двух важных правил, называемых соответственно правилами сложения и умножения.

Правило умножения (основной принцип): если из некоторого конечного множества первый объект (элемент ) можно выбрать способами и после каждого такого выбора второй объект (элемент ) можно выбрать способами, то оба объекта ( и ) в указанном порядке можно выбрать способами.

Этот принцип распространяется на случай трёх и более объектов.

Пример 1. Сколько трёхзначных чисел можно составить из цифр , если: а) цифры не повторяются? б) цифры могут повторяться?

Подсчитаем число способов выбора цифры для первого места слева

в трёхзначном числе (эти места помечены звёздочками) . Коль скоро цифр 5 то очевидно, что на первое место в трёхзначном числе можно поставить любое из указанных чисел. Поэтому число способов выбора равно 5. После того как первое место занято, например, то осталось четыре цифры для заполнения второго места. После заполнения второго места, например, для заполнения третьего места остаётся выбор из трёх цифр. Например, . Поэтому согласно правилу умножения имеется способов расстановки цифр, т.е. искомое число трёхзначных чисел есть . Если цифры могут повторяться, то трёхзначных чисел будет .

Правило суммы. Если некоторый объект можно выбрать способами, а объект можно выбрать способами, причём первый и второй способы не пересекаются, то любой из указанных объектов ( или ), можно выбрать способами.

Это правило распространяется на любое конечное число объектов.

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

По правилу умножения двух девушек можно выбрать способами, а двух юношей - способами. Следует выбрать студентов одного пола: двух студенток или двух юношей. Согласно правилу сложения таких способов выбора будет .

Существуют две схемы выбора элементов из различных элементов рассматриваемого множества: без возвращения (без повторений) и с возвращением (с повторением). В первом случае выбранные элементы не возвращаются обратно; можно отобрать сразу все элементов или последовательно отбирать их по одному. Во второй схеме выбор осуществляется поэлементно с обязательным возвращением отобранного элемента на каждом шаге.