04. Некоторые комбинаторные формулы

Как правило, подсчет вероятностей по классической формуле сводится к решению чисто комбинаторных задач. Приведем наиболее часто используемые комбинаторные формулы.

1. Число перестановок. Пусть N элементов А1, A2 ,…,АN надо разместить по N позициям.

Сколькими способами это можно сделать? В первую позицию можно поместить любой из этих элементов (N различных вариантов), во вторую - любой из (N – 1) - ого оставшегося, для заполнения третьей позиции существует только (N – 2) варианта, и т. д. Общее число различных Перестановок равняется
N*(N – 1)*(N – 2)*…*1 = N!

2. Число размещений. Пусть теперь M элементов из N (M < N) надо разместить по M позициям.

Такие комбинации называются Размещениями. Общее число размещений из N элементов по M обозначается и равняется N * (N – 1)*(N – 2)*…*(N –m + 1),
т. к. существует n вариантов разместить элемент в первой позиции, (N – 1)- во второй,…, (N – M + 1) элемент - в M-ой позиции Итак,

3. Число сочетаний. Рассмотрим выборки из N элементов по M (M < N), отличающиеся только составом, без учета порядка, в котором они выбираются. Такие комбинации называются Сочетаниями. А поскольку М элементов можно переставлять M! способами, общее число сочетаний Cnm будет в M! раз меньше, чем общее число размещений.

4. Число размещений с повторениям. Будем теперь, выбирая элемент из N элементов, запоминать его номер, а элемент возвращать обратно. Комбинации, которые могут получиться при таком M-кратном выборе, называются Размещениями с повторениями. Общее число размещений с повторениями обозначается Ãnm и, очевидно, равняется Nm .

5. Число сочетаний с повторениями. Выборку из N элементов по M с возвращением можно производить и без учета порядка, в котором элементы выбираются. Общее число получающихся при таком выборе Сочетаний с повторениями Čnm = Cn+m-1m .

Докажем эту формулу по индукции. При M = 2 существуют следующие сочетания с повторениями из N элементов:

(А1,А1),(А1,А2),(А1,А3)……………(А1,Аn) N сочетаний

(А2,А2),(А2,А3)……………(А2,Аn) (N – 1) cочетание

(А3,А3)……………(А3,Аn) (N – 2) cочетания

……………………………………… ………………..

(Аn, аn) 1 сочетание

Всего cочетаний с повторениями из N элементов по 2: N + (N – 1) + (N –
– 2) +…+ 1 = (N + 1)*N/2 = Cn+12.

Предположим, формула Čnk = Cn+K-1K верна при всех K от 2 до (M – 1), докажем ее для K = M.

При выборе M элементов из N c возвращением какие-то J позиций из M заняты элементами, которые встречаются первый раз, а M – J позиций - сочетаниями с повторениями из этих J элементов (по предположению индукции их
Čjm - J = Cm – 1M-j ) . Следовательно,

Čnm = ΣJ = 1M Cnj * Cm - 1M – J.

Ecли рассмотреть сочетания без повторения из N + M – 1 элемента по M, то их столько же: на J позиций выбираются элементы из N, а на (M – j) позиций - из (M – 1), т. е.

Cn + M – 1M = ΣJ = 1M Cnj * Cm – 1M – J.

Поэтому, Čnm = Cn + M – 1M. ♣

Пример 3. Рассмотрим игру в преферанс, когда старшие 32 карты карточной колоды сдаются по 10 трем игрокам, а две карты кладутся в “прикуп”. Какова вероятность, что в прикупе окажутся два туза?

Число различных комбинаций из двух карт, которые могут оказаться в прикупе, равно числу сочетаний С322 = 32! / (2! * 30!) = 496. Эти сочетания и образуют пространство элементарных событий W. В карточной колоде 4 туза. Число элементарных событий, дающих два туза, равно числу сочетаний С42 = 4!/(2!*2!)=6. Вероятность двух тузов в прикупе Р(А) = 6/496 = 0,012…¨

< Предыдущая		Следующая >