1.4 Соединения или комбинации

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

Решить эту задачу можно с привлечением методов комбинаторики

1.4.1. Размещения и перестановки

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

Предметы, из которых составляются соединения, называются элементами.

Частными видами соединений являются размещения, перестановки и сочетания.

Размещениями из n элементов по m называются такие соединения, из которых каждое содержит m элементов, взятых из данных n элементов, и которые отличаются одно от другого или элементами, или порядком элементов (предполагается, что ).

Пусть, например, число предметов, из которых мы составляем различные соединения равно трем; обозначим эти предметы a, b и c. Из них можно составить соединения по одному:

a, b, c;

по два:

ab, ac, ba, bc, ca, cb;

по три:

abc, acb, bac, bca, cab, cba.

Из этого примера виден способ построения размещений. Число возможных размещений по 1 совпадает с общим числом элементов равных в данном случае 3.

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

3 - 1=2. Таким образом, полное число размещений из трех по 2 равно . Аналогично строятся размещения в общем случае, когда число элементов равно n.

Число всевозможных размещений из n элементов по m обозначим как .

Из описанного выше способа построения размещений ясно, что , аналогично,

и вообще,

.

При m=n все возможные размещения представляют собой все возможные перестановки исходных элементов.

Их число , то есть равно произведению все чисел от 1 до n, которое обозначается как (читается: n-факториал).

1.4.2. Соединения и выборки

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

Таким образом, в конкретной выборке каждый элемент может встречаться несколько раз.

Все возможные выборки с возвращением, которые можно сформировать из элементов трех типов a, b и c по 2, будут такие (сравни с предыдущим случаем):

aa, ab, ac, ba, bb, bc, ca, cb, cc;

Для формирования всех таких соединений по 2 надо записать строку исходных элементов дважды

a, b, c…

a, b, c…

и каждый элемент первой строки последовательно объединять со всеми элементами второй строки.

Если полное число элементов есть n, то число возможных соединений по 2 равно .

Итак, если объем выборок равен m, то необходимо записать m строк и, следовательно, количество упорядоченных выборок с возвращением будет равно .

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

и называют убывающий m-факториал.

Очевидно, что при m=n справедливо следующее равенство:

Примеры.

1. Сколько двоичных кодов можно записать на 8-разрядной сетке?

Число таких кодов, например 01101001, совпадает с числом возможных выборок с возвращением объема 8 из двух элементов 0 и 1.

Следовательно, m=8 и n=2, ответом будет число равное .

2. Сколько целых трехзначных чисел можно записать, используя 10 десятичных цифр 0, 1, …,9

Из 10 элементов (цифр) можно сформировать выборок с возвращением по 3. Однако, выборки, имеющие 0 на первой позиции, соответствуют либо двузначным, либо однозначным числам, либо нулю и их надо исключить. Таких комбинаций будет столько, сколько возможно выборок с возвращением из 10 элементов по 2, то есть . Следовательно, трехзначных чисел будет .

Выбор m элементов из генеральной совокупности объема n является экспериментом, возможными исходами которого являются различные выборки объема m. Общее число их равно или , в зависимости от того, как производится выбор: с возвращением или без возвращения. Предположим, что выбор производится случайно и так, что все выборки равновероятны.

Какова вероятность, что случайно извлеченная выборка с возвращением не имеет одинаковых элементов, то есть эта выборка является размещением и могла бы быть получена при выборе без возвращения?

Воспользуемся формулой благоприятных исходов.

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

Таким образом, искомая вероятность равна

.

Если объем генеральной совокупности n велик, а m сравнительно мало, то отношение близко к единице. Это говорит о том, что при большой генеральной совокупности и относительно малой выборке различие между двумя способами выбора незначительно, и .

В следующих примерах раскрывается неожиданное свойство приведенной выше вероятности.

Примеры.

1. Имеется группа из m случайно выбранных людей. Какова вероятность, что все люди из этой группы имеют различные дни рождения? Для простоты можно игнорировать существование високосных годов и принять, что в году 365 дней.

Дни рождения m произвольно выбранных людей образуют случайную выборку объема m с возвращением из всех дней в году. Нас интересуют те выборки, элементы которых различны. Вероятность выбора одной из них равна

Расчеты по этой формуле приведут нас к парадоксальным результатам. Для малой выборки кажется правдоподобным заключение, что p близко к единице. И действительно, для m = 10 человек p = 0.883. Однако, уже для m = 23, что тоже невелико, p < 0.5, то есть в более 50% групп с такой численностью найдутся, по крайней мере, двое, имеющие общий день рождения.

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

Решение сводится к случайному выбору с возвращением семи дней недели, для семи катастроф . Объем выборки m =7 равен числу элементов n =7, из которых производится выбор. Напомним, что , и приведенная выше формула для вероятности выборки с различающимися элементами даст: .

Таким образом, равномерное распределение числа катастроф встречается очень редко, в среднем лишь для одной недели из 163. Обычно, на какие то дни недели приходится две и более катастроф. Удивительно, что этот вывод следует из предположения о равной вероятности всех дней недели в отношении возможных катастроф.

3. Какова вероятность, что при шести бросаниях правильной кости появятся все возможные грани?

Ситуация аналогична рассмотренной в предыдущем примере. Через  обозначим последовательность номеров граней, появившихся в серии из 6 бросаний. Полное число вариантов равно числу выборок с возвращением из 6 по 6 элементов. Благоприятными являются выборки без возвращений из 6 по 6 элементов (перестановки). Интересующая нас вероятность есть - это всего 1.5%, что, на первый взгляд, также противоречит представлению о равной вероятности выпадения всех граней.