§10. Комбинаторика.

Решение вероятностных задач на классическую схему часто облегчается использованием комбинаторных формул. Каждая из комбинаторных формул определяет общее число элементарных исходов в некотором опыте, состоящем в выборе наудачуmэлементов изnразличных элементов исходного множестваM={x₁,x₂,…,x_n}. При этом в постановке каждого такого опыта строго оговорено, каким образом производится выбор и что понимается под различными выборками.

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

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

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

.

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

.

Замечание.Примем по определению равенство 0!=1.

2. Схема выбора, приводящая к размещениям с повторениями. Выборmэлементов из множества М={x₁,x₂,…,x_n} производится с возвращением и с упорядочиванием. Различными исходами будут всевозможныеm-элементные наборы (вообще говоря, с повторениями), отличающиеся либо составом элементов, либо порядком их следования. Например приm=4 множества (строки)исчитаются различными исходами данного опыта. Полученные в результате комбинации называютсяразмещением с повторениямиизnэлементов поm. Их общее число определяется формулой

Пример 1. 7 одинаковых шариков случайным образом рассыпают по 4 лункам (в одну лунку может поместиться любое число шариков). Сколько существует различных способов распределения 7 шариков по 4 лункам? Какова вероятность того, что в результате данного опыта первая лунка окажется пустой (при этом может оказаться пустой и еще какая-либо лунка)?

Решение. Занумеруем лунки и шарики. Можно считать, что опыт состоит в 7-кратном выборе с возвращением номера лунки. Строка (х₁,х₂,…,х₇) полностью характеризует распределение шариков по лункам (х_i – номер лунки в которую попалi-ый шар). Каждое из чиселх₁,х₂,…,х₇может принимать любое целое значение (номер лунки) от 1 до 4. Так, например, строка (1,1,3,1,4,4,2) означает, что в первую лунку попали шары с номерами 1,2,4, во вторую лунку – шар №7, в третью – шар №3, в четвертую – шары №5 и №6. Таким образом, число всех распределений 7 шариков по 4 лункам равно числу различных строк длиной 7 из множестваM={1,2,3,4}. Следовательно, их будет.

Событие А={первая лунка окажется пустой} соответствует такому выбору, когда номер 1 (номер первой лунки) удалён из строки. Поэтомуи значит.

Пример 2. Множество М состоит из 10 первых букв русского алфавита. Опыт состоит в выборе без возвращения 4 букв и записи слова в порядке поступления букв. Сколько 4-буквенных слов может быть получено в данном опыте? Какова вероятность того, что наудачу составленное слово будет оканчиваться буквой «а» (событиеА)?

Решение.– число всех 4-буквенных слов в данном опыте – равно числу 4-элементных упорядоченных подмножеств множества из 10 букв, т.е..

Событию Асоответствует число способов разместить на 3 оставшихся места по одной букве из 9 (буква «а» исключена из рассмотрения, поскольку её место уже определено). Таким образоми значит.

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

.

Числа называютсябиномиальными коэффициентами.

Для них справедливы следующие тождества, полезные при решении задач:

1. (свойство симметрии)

2. (рекуррентное соотношение)

3. Имеет место следующая формула, называемая формулой бинома Ньютона

.

Пример 3(задача о выборке). Из партии, содержащейnизделий, среди которыхn₁бракованных, наудачу извлекаютmизделий для контроля. Найти вероятность следующего событияА={в полученной выборке содержится ровноm₁бракованных изделий}.

Решение.Занумеруем изделия числами от 1 доn. Согласно описанию эксперимента производится выбор без возвращения и без упорядочиванияmэлементов изn. Поэтому число таких выборок равна.CобытиюАблагоприятствуют такие исходы когдаm₁элемент выборки изmизделий принадлежит множеству избракованных изделий, а остальныеm-m₁изделие этой выборки принадлежит множеству изm-не бракованных изделий. Число всех таких исходов равно(поскольку на каждую выборкуm₁бракованных изделий избракованных приходитсявыборокm-m₁не бракованных изделий из общего числаn-не бракованных). Окончательно получаем

.

4. Схема выбора, приводящая к сочетаниям с повторениями.Опыт состоит в выборе с возвращениемmэлементов множества М={ x₁,x₂,…,x_n}, но без последующего упорядочивания, то есть различными исходами такого опыта будут всевозможныеm-элементные наборы, отличающиеся составом. Например, приm=4 наборыинеразличимы для данного эксперимента, а наборотличен от любого из предыдущих. Получающиеся в результате данного опыта комбинации называютсясочетаниями с повторениями, а их общее число определяется формулой

.

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

5. Размещения данного состава. Полиномиальная формула. Пусть– строка длинойк, составленная из элементов упорядоченного множестваX={a₁,а₂,…,а_n}, состоящего изn-элементов. Тогда каждому номеру iиз совокупности 1,2,…, nбудет соответствовать числок_i, показывающее, сколько раз элемент а_iвстречается в строке. Выписывая по порядку эти числа, получаем новую строку (к₁, к ₂,…, к _n), которую называют составом строки. Например, еслиX={а₁,а₂,а₃,а₄} и, то строка имеет состав (3,0,2,1) (в ней элемент а₁встречается 3 раза, элемент а₂– 0 раз, а₃– 2 раза, а₄– 1 раз). Две строки, имеющие один и тот же состав, могут отличаться друг от друга лишь порядком номеров. Их называютразмещениями (с повторениями) данного состава. Число размещений имеющий данный состав (к₁, к₂,…, к_n ) будет выражаться следующей формулой

.

Аналогично формуле Бинома Ньютона, имеет место полиномиальная формула

,

где суммирование в правой части формулы производится по всевозможным наборам целых неотрицательных чисел к₁,к₂,…,к_n таких, что к₁+к₂+…+к_n=к.

Пример 4. Игральную кость бросают 10 раз. Какова вероятность, что при этом грани 1,2,3,4,5,6 выпадут соответственно 2,3,1,1,1,2 раза (событиеА),

Решение.Число всех строк длиной 10 из элементов множестваX={1,2,3,4,5,6} равно. благоприятными дляАбудут строки, в которых элементы 1,2,3,4,5,6 встречаются соответственно 2,3,1,1,1,2 раза, т.е. строки, имеющие состав (2,3,1,1,1,2). Число таких строк будет равно:

Отсюда искомая вероятность будет равна .

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

Пример 5. В урне имеетсяnшаров; из них:n₁шаров 1-го цвета,…,n_iшаровi-го цвета,…,шаровm-го цвета (n₁+n₂+…+n_m=n). Из урны вынимается одновременнок шаров. Найти вероятность того, что среди них будет:к₁шаров 1-го цвета,…,к_mшаровm-го цвета, гдек₁+к₂+…+к_m=к(событиеА).

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

Так как группу шаров первого цвета можно выбрать способами, группу шаров второго цветаспособами и т.д. Искомая вероятность будет равна

.