Материал: Чернова Н.И. - Теория вероятностей - 1999

— Знаете что, милый Арамис? — сказал д’Артаньян, ненавидевший стихи почти так же сильно, как латынь. — Добавьте к достоинству трудности достоинство краткости, и вы сможете быть уверены в том, что ваша поэма будет иметь никак не менее двух достоинств.

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

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

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

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

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

N = n1 n2 : : : nk:

Замечание 1. В теореме 1 считается, что даже если все элементы в i-й группе неразличимы, выбрать один из них можно ni способами. Представим результат выбора, описанного в теореме 1, в виде набора (a1; : : : ; ak), в котором ai — выбранный из i-й группы элемент. Тогда общее число различных наборов (a1; : : : ; ak) также равняется

N = n1 n2 : : : nk.

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

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

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

Упражнение 1. Сформулировать предположение индукции и доказать индукционный переход от k 1 к k.

1

Урны и шарики

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

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

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

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

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

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

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

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

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

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

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

k

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

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

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

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

2

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

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

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

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

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

Теорема 4. Общее количество выборок в схеме выбора k элементов из n с возвра-

способов второй шарик можно выбрать также n способами, и так k раз.

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

Рассмотрим урну с двумя шариками и перечислим результаты выбора двух шариков из этой урны при выборе с возвращением:

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

Cnk+k 1 = Cnn+k1 1:

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

Доказательство. Рассмотрим подробно, чем отличаются друг от друга два разных результата такой схемы выбора.

Нам не важен порядок номеров, то есть мы учитываем только, сколько раз в нашем наборе из k номеров шариков появился шарик номер 1, шарик номер 2, : : : , шарик номер n. То есть результат выбора можно представить набором чисел k1; k2; : : : ; kn, в котором ki — число появлений шарика номер i в выборке, и k1 + : : : + kn = k. Числа ki принимают значения из N [ f0g. При этом два результата эксперимента различны,

3

если соответствующие им наборы k1; k2; : : : ; kn не совпадают (при этом учитывается и порядок элементов).

Представим себе другой эксперимент, имеющий точно такие же результаты (и, следовательно, их столько же). Есть n ящиков, в которых размещается k шариков. Нас интересует только количество шариков в каждом ящике. То есть результатом эксперимента снова является набор чисел k1; k2; : : : ; kn, в котором ki — число шариков в ящике с номером i, и k1 +: : :+kn = k. Числа ki по-прежнему принимают натуральные значения или равны 0.

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

Мы видим результат размещения 9 шариков по 7 ящикам. Здесь 1-й ящик содержит 3 шарика, 2-й и 6-й ящики пусты, 3-й ящик содержит 1 шарик, и в 4-м и 5-м ящиках есть по 2 шарика. Переложим один шарик из первого ящика во второй и изобразим таким же образом еще один результат размещения:

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

Но способов расставить k шариков на n 1+k местах ровно Cnk 1+k — это в точности число способов выбрать из n 1+k номеров мест k номеров мест (без учета порядка и без возвращения), на которые нужно поместить шарики. Заметим, что равенство Cnk+k 1 = Cnn+k1 1 верно как по определению биномиальных коэффициентов или свойствам треугольника Паскаля, так и в силу того, что можно вместо выбора k мест для шариков выбирать n 1 место для перегородок ящиков, заполняя шариками оставшиеся места.

4