Раздел 1. Классическая вероятностная схема

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

В данном разделе мы займемся подсчетом числа «шансов». О числе шансов говорят, когда возможно несколько различных результатов какого-либо действия (извлечение карты из колоды, подбрасывание кубика или монетки, двух кубиков и т.д.). Число шансов — это число таких возможных результатов, или, иначе говоря, число способов проделать это действие.

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

Теорема 1. Пусть имеется, k групп элементов, причем i-я группа содержит ni элементов, 1<=i<=k. Выберем из каждой группы по одному элементу. Тогда общее число N способов, которыми можно произвести такой выбор, равняется

Замечание 1. В теореме 1 считается, что даже если все элементы в i-й группе неразличимы, выбрать один из них можно ni способами.

Замечание 2. Результат выбора, описанного в теореме 1, представим в виде набора (а1, а 2,…, а k) в котором аi — выбранный из i-й группы элемент. Тогда общее число различных наборов (а1, а 2,…, а k) также равняется

Доказательство теоремы 1.

Занумеруем элементы i -ой группы числами от 1 до ni. Элемент из первой группы можно выбрать n1 способами. Если мы выбрали элемент j, 1<=i<= n1, то выбрать элемент из второй группы мы можем n2 способами. Получаем, что с первым элементом j возможно составить n2 пар (j, l), где 1<=l<= n2.

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

Иначе говоря, есть способов выбрать по одному элементу из первых двух групп. Возьмем одну такую пару (j, l). Заметим, что элемент из третьей группы можно выбрать n3 способами, то есть возможно составить ровно n3 троек (j, l, m), добавляя к данной паре (j, l) любой из n3 элементов третьей группы.

Но столько же троек можно составить и с любой другой парой (j, l). Тогда всего троек, в которых первый элемент выбран из первой группы, второй — из второй, а третий — из третьей, существует ровно .

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

Урны и шарики

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

На этот вопрос нельзя дать однозначный ответ, пока мы не определимся

· с тем, как организован выбор (скажем, можно ли шарики возвращать в урну), и

· с тем, что понимается под различными результатами выбора.

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

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

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

И в том, и в другом случае результатом выбора является набор из k номеров шариков. Удобно считать, что шарики всегда выбираются последовательно, по одному (с возвращением или без).

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

Есть ровно две возможности.

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

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

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

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

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

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

Доказательство. Первый шарик можно выбрать n способами. При каждом из этих способов второй шарик можно выбрать n-1 способом, и т.д. Последний k-й шарик можно выбрать (n-k+1) способом. По теореме 1, общее число способов выбора равно

что и требовалось доказать.

Следствие 1. Число возможных перестановок множества из n элементов есть n!

Доказательство очевидно, если заметить, что перестановка есть не что иное, как результат выбора без возвращения и с учетом порядка всех n элементов из n. Так что общее число перестановок равно

Урновая схема: выбор без возвращения и без учета порядка

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

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

Доказательство. Заметим, что, согласно следствию 1, из каждой выборки данного состава (состоящей из k элементов) можно образовать k! выборок, отличающихся друг от друга только порядком элементов.

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