Число размещений (выбор без возвращения)

Предположим, что r различных предметов размещаются по n ячейкам (в каждую ячейку можно поместить только один предмет).

Занумеруем все ячейки и все предметы. Тогда каждое размещение можно описать комбинацией вида , где i₁ - номер ячейки, в которую попал 1–ый предмет, i₂ - номер ячейки, в которую попал 2–ой предмет,…, i_r - номер ячейки, в которую попал r–ый предмет. Согласно формуле пункта 1 ( ), всего существует следующее число указанных размещений

.

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

При r=n получим .

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

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

Число сочетаний.

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

.

Вышеприведенная формула также определяет число подмножеств размерности r множества из n элементов, где два подмножества считаются различными, если они отличаются элементами, а порядок их следования – несущественен. Соответственно в знаменателе имеем деление на r!.

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

Результат разбиения можно представить в виде вектора размерности n, содержащего r единиц (признак незанятости ячейки) и (n-r) двоек (признак занятости ячейки). Два разбиения различны, если различны соответствующие им вектора.

Рассмотрим общий случай разбиения n различных элементов на k групп, причем в группе с номером i число элементов равно n_i и . Результат разбиения вновь можно представить в виде вектора размерности n, содержащего n₁ единиц, n₂ двоек, …, n_k чисел k. Два разбиения различны, если различны соответствующие им вектора. Число различных разбиений дается формулой

.

Пример 1: N различных шаров случайно размещаются по М ящикам, М>N.

Найти вероятность, что все шары попадут в разные ящики.

Решение.

Число способов размещения N шаров по М ящикам равно М^N.

Число способов размещения N шаров по М ящикам, когда в каждый ящик попадает по одному шару равно

.

Ответ:

Пример 2: (гипергеометрическое распределение вероятностей).

Существует большой класс задач ТВ, которые можно интерпретировать в рамках так называемой урновой схемы: событие, вероятность которого надо вычислить, можно трактовать как выбор шаров различной расцветки из урны. Простейшая из таких схем состоит в следующем. Из урны, содержащей М черных и N-M белых шаров, случайно вынимается n шаров. Какова вероятность того, что выборка содержит m черных шаров?

Решение.

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

Очевидно что, .

Правая часть неравенства означает, что число черных шаров m должно быть меньше объема выборки n и числа M черных шаров.

Левая часть неравенства означает, что если объем выборки n превышает число белых шаров N-M, то число черных шаров не может быть меньше, чем n-(N-M) = (размер выборки – число белых шаров).

Число способов выбора из М черных шаров m шаров равно . Число способов выбора из N-M белых шаров n-m шаров равно .

Следовательно общее число исходов, соответствующее событию А – «выборка содержит m черных шаров» равно , и искомая вероятность Р(А)= / .

Пример3: (Задача про рыб).

Из озера вылавливается 1000 рыб. Каждая из рыб метится красной меткой и отпускается в озеро. При следующем улове среди 1000 рыб оказалось 100 меченых. Какие выводы можно сделать относительно числа рыб?

Решение.

Пусть n – (неизвестное) число рыб в озере, n₁-число меченых рыб (n₁=1000), r – число рыб, пойманных при втором улове (r=1000), k- число меченых рыб, пойманных при втором улове (k =100).

Вероятность поймать k меченых рыб есть

.

Для оценки числа рыб n предлагается найти n из условия максимума вероятности , то есть в предположении, что при втором улове реализовалось наиболее вероятное событие. Основной довод в пользу такой оценки числа рыб состоит в простом житейском наблюдении: если происходит какое-либо событие, то это событие должно иметь наибольшую вероятность среди всех остальных исходов.

Для определения максимума вероятности по переменной n, рассмотрим

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