Элементы комбинаторики

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

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

Упорядоченные наборы, т. е. наборы, отличающиеся не только составом элементов, но и их порядком следования, называют размещениями, а неупорядоченные – сочетаниями. Например, из множества , выбирая по два элемента ( ) можно образовать шесть размещений: , , , , , ; и три сочетания , , . Сочетание можно записать и в виде , так как при образовании сочетаний по определению порядок элементов не учитывается. Размещения из элементов по называют перестановками. Различные перестановки содержат одни и те же элементы, расположенные в разном порядке. В нашем примере таких перестановок шесть: , , , , , .

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

. (3)

Напомним, что по определению - факториал , причем .

Для имеет место также следующее рекуррентное соотношение:

.

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

.

Для справедлива следующая рекуррентная формула:

.

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

.

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

(свойство симметрии),

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

(следствие биномиальной формулы Ньютона).

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

А. Схема выбора, приводящая к сочетаниям без повторений элементов. Если опыт состоит в случайном выборе элементов без возвращения и без упорядочивания, то различными элементарными исходами будут - элементные подмножества множества , имеющие различный состав, т. е. сочетания из элементов по . Таким образом, общее число элементарных исходов опыта в этом случае

= .

Пример. Из урны, содержащей 10 белых и 5 черных шаров, наудачу без возвращения извлекается три шара. Какова вероятность извлечь три белых шара?

◄ Слово «наудачу» в условии задачи означает, что шары были хорошо перемешаны, что все они одного диаметра, одинаково гладкие и отличаются только цветом; выбирающий шаров не видит. В таком случае разумно предположить равновероятность элементарных исходов и воспользоваться классическим определением вероятности. За элементарные исходы естественно принять любые подмножества по три элемента, выбранные из множества из 15 шаров. Так как порядок извлеченных шаров нас не интересует, то под исходом следует понимать любое сочетание трех элементов из 15. Число таких сочетаний = . Событию ={все три извлеченных шара окажутся белыми} благоприятствует исходов (вынимаются какие-то три белых шара из 10 белых): = . По формуле классической вероятности находим: . ►

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

= .

В частном случае опыт фактически состоит в произвольном упорядочивании множества , т. е. сводится к случайной перестановке элементов всего множества. В этом случае

= .

Пример. На пяти карточках написаны цифры от 1 до 5. Опыт состоит в случайном выборе трех карточек и раскладывании их в порядке поступления слева направо. Найти вероятность события ={появится число, не содержащее цифры 3}.

◄ В качестве равновероятных элементарных исходов данного опыта выступают упорядоченные наборы трех карточек из пяти (размещения из пяти элементов по три). Их общее число = . Наборы, благоприятствующие рассматриваемому событию, представляют также упорядоченные наборы трех карточек, но из четырех карточек (цифру 3 исключаем из исходного множества), т. е. = . По формуле классической вероятности получаем: . ►

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

= .

Пример. В кондитерской имеется 7 видов пирожных. Очередной покупатель приобрел 4 пирожных. Считая, что любой набор пирожных равновероятен, найти вероятность того, что покупатель приобрел по два пирожных различных видов.

◄ Число всех равновероятных исходов данного опыта равно, очевидно, числу сочетаний с повторениями из 7 элементов по 4, т. е. = .

Число исходов, благоприятствующих событию ={в наборе по два пирожных различных видов}, равно числу способов выбрать два элемента из семи, поэтому . ►

Г. Схема выбора, приводящая к размещениям с повторениями элементов. Если выбор элементов из множества производится с возвращением и с упорядочиванием их в последовательную цепочку, то различными исходами будут всевозможные - элементные наборы, среди которых будут с повторениями элементов, отличающиеся либо составом элементов, либо порядком их следования. Например, при множества , и будут различными исходами данного опыта, а их общее число определяется формулой

= .

Пример. Бросается пять игральных костей. Найти вероятность того, что на них выпадут различные цифры.

◄ Бросание пяти игральных костей смоделируем схемой урн: из урны, в которую помещены 6 карточек с нанесенными на них цифрами от 1 до 6, выбираем наудачу с возвращением пять раз карточки с упорядочиванием их в последовательную цепочку. Появление той или иной цифры на карточке в цепочке будет соответствовать выпадению этого числа очков на соответствующей кости.

Очевидно, что элементарные исходы в данном опыте представляют собой размещения с повторениями при и , т. е. = . Событию ={все цифры на костях различны} благоприятствуют размещения, в которых элементы (цифры) не повторяются, т. е. = . Таким образом, . ►