Схема выбора, приводящая к размещениям

Комбинаторика

При подсчете числа элементарных исходов опыта, составляющих события в классической схеме, часто используются известные формулы комбинаторики. Каждая из комбинаторных формул определяет общее число элементарных исходов в некотором эксперименте по выбору наудачу m элементов из n различных элементов исходного множества E = {e₁, e₂,..., e_n}.

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

1. Схема выбора, приводящая к сочетаниям

Если опыт состоит в выборе m элементов без возвращения и без упорядочивания, то различными исходами следует считать m-элементные подмножества множества E, имеющие различный состав. Получаемые при этом комбинации элементов (элементарные исходы) носят название сочетания из n элементов по m, а их общее число N определяется по формуле:

C^m_n =

Для чисел C^m_n, называемых также биномиальными коэффициентами, справедливы следующие тождества, часто оказывающиеся полезными при решении задач:

C^m_n = C^n-m_n (свойство симметрии),

C⁰_n + C¹_n +... + Cⁿ_n = 2ⁿ.

Пример 1. Множество Е содержит 10 первых букв русского алфавита. Сколько различных алфавитов из трех букв можно составить из данного множества букв?

Решение Число различных алфавитов равно числу трехэлементных подмножеств множества Е (числу сочетаний из 10 элементов по 3):

N = C³₁₀ = .

Схема выбора, приводящая к размещениям

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

= ×m! =

Если n=m, то опыт состоит в произвольном упорядочивании множества Е, т.е. сводится к случайной перестановке элементов всего множества. В этом случае говорят о перестановках из n элементов. Тогда N = = n!.

Пример 2. Группа, состоящая из 8 человек, занимает места за круглым столом в случайном порядке. Какова вероятность того, что при этом два определенных лица окажутся сидящими рядом?

Решение. Так как упорядочивается все множество из 8 элементов, то

N = A = Р₈= 40320.

Формула Бернулли.

Предположим, что производится n независимых опытов, в результате каждого из которых может наступить или не наступить некоторое событие A. Пусть при каждом опыте вероятность наступления события А равна P(A)=p и, следовательно, вероятность противоположного события (ненаступления А) равна

.

Определим вероятность P_m,n того, что событие А произойдет m раз при n опытах. При этом заметим, что наступления или ненаступления события А могут чередоваться различным образом. Условимся записывать возможные результаты испытаний в виде комбинаций букв А и . Например, запись означает, что в четырех испытаниях событие осуществилось в 1-м и 4-м случаях и не осуществилось во 2-м и 3-м случаях.

Всякую комбинацию, в которую А входит m раз и входит n-m раз, назовем благоприятной. Количество благоприятных комбинаций равно количеству k способов, которыми можно выбрать m чисел из данных n; таким образом, оно равно числу сочетаний из n элементов по m, т.е. k = C

Подсчитаем вероятности благоприятных комбинаций. Рассмотрим сначала случай, когда событие A происходит в первых m опытах и, следовательно, не происходит в остальных n-m опытах. Такая благоприятная комбинация имеет следующий вид:

Вероятность этой комбинации в силу независимости испытаний составляет

Так как в любой другой благоприятной комбинации В_i событие A встречается также m раз, а событие происходит n-m раз, то вероятность каждой из таких комбинаций также равна p^mq^n-m. Итак,

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

Следовательно,

;

Формула (13) называется формулой Бернулли.