Основные формулы комбинаторики

Теорема о перемножении шансов

Пусть одно действие можно проделать пятью способами, а другое — двумя. Каким числом способов можно проделать пару этих действий?

Теорема 1. Пусть множество состоит из элементов:, а множество — из элементов:. Тогда можно образовать ровно пар, взяв первый элемент из множества, а второй — из множества.

Замечание 1. Можно сформулировать утверждение теоремы 1 так: если первый элемент можно выбрать способами, а второй элемент — способами, то пару элементов можно выбрать способами.

Доказательство. С элементом мы можем образовать пар:. Столько же пар можно составить с элементом, столько же — с элементом и с любым другим из элементов множества. Т.е. всего возможно пар, в которых первый элемент выбран из множества, а второй — из множества.

Упражнение 1. С помощью теоремы 1 доказать, что:

а)при подбрасывании трёх монет возможно 2·2·2=8 различных результатов;

б) бросая дважды игральную кость, получим 6·6=36 различных результатов;

в) трёхзначных чисел бывает 9·10·10=900;

г) трёхзначных чисел, все цифры которых различны, существует 9·9·8;

д) чётных трёхзначных чисел возможно 9·10·5.

Урны и шарики

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

Рассмотрим следующие возможные способы выбора.

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

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

Условимся, какие результаты выбора (наборы из номеров шаров) мы будем считать различными. Есть ровно две возможности.

1. Выбор с учётом порядка: два набора номеров шаров считаются различными, если они отличаются составом или порядком номеров. Так, при выборе трёх шаров из урны, содержащей 5 шаров, наборы (1, 5, 2), (2, 5, 1) и (4, 4, 5) различны, если порядок учитывается.

2. Выбор без учёта порядка: два набора номеров шаров считаются различными, если они отличаются составом. Наборы, отличающиеся лишь порядком следования номеров, считаются одинаковыми.

Так, наборы (1, 5, 2) и (2, 5, 1) не различаются и образуют один и тот же результат выбора, если порядок не учитывается.

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

Выбор без возвращения, с учётом порядка

Теорема 2. Общее количество различных наборов при выборе элементов из без возвращения и с учётом порядка равняется

 

и называется числом размещений из элементов по элементов.

QED

Следствие 1. Если в множестве элементов, то существует ровно > перестановок этих элементов.

Доказательство. Перестановка — результат выбора без возвращения и с учётом порядка элементов из. Поэтому общее число перестановок равно

QED

Теорема 3. Общее количество различных наборов при выборе элементов из без возвращения и без учёта порядка равняется

 

и называется числом сочетаний из элементов по элементов.

QED

Теорема 4. Общее количество различных наборов при выборе элементов из с возвращением и с учётом порядка равняется >.

Доказательство. Первый шар можно выбрать способами. При каждом из этих способов второй шар можно выбрать также способами, и так раз. Общее число наборов равно .

QED

Теорема 5. Общее количество различных наборов при выборе элементов из с возвращением и без учёта порядка равняется

Упражнение 6. Проверить, что при и получается ровно 3.

Доказательство. Рассмотрим подробно, чем отличаются друг от друга два разных результата такой схемы выбора. Нам не важен порядок номеров, т.е. мы учитываем только, сколько раз в нашем наборе из номеров шаров появился каждый номер. Поэтому результат выбора можно представить набором чисел , в котором — число появлений шара номер в наборе, и . Числа принимают значения из . Два результата выбора в схеме выбора с возвращением и без учёта порядка различаются, если соответствующие им наборы не совпадают (порядок следования элементов учитывается).

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

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

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

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

Осталось заметить, что способов расставить шаров на местах существует

Именно столько есть способов выбрать из номеров мест номеров мест для шаров.