Случайные величины и их распределения

Основные формулы комбинаторики

В предоставленном разделе мы займемся подсчетом количества «шансов». О количестве шансов говорят, как скоро возможно некоторое количество разных итогов какого-либо действия (извлечение игра в карты из колоды, подбрасывание кубика либо монетки, 2-ух кубиков и т. д.). Количество шансов — это количество таких вероятных итогов, либо, иначе говоря, количество методик сделать это действие.

Теорема о перемножении шансов. Пускай имеется, k групп частей, причем i-я категория охватывает n_i частей, 1<=i<=k. Подберем из каждой категории по 1 составляющей. Тогда общее количество N методик, которыми разрешено произвести таковой отбор, приравнивается.

ы (8).

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

Примечание 2. Итог выбора, описанного в теореме 1, предположим в виде комплекта (а₁, а ₂,…, а _k) в котором а_i — избранный из i-й категории элемент. Тогда общее количество разных комплектов (а₁, а ₂,…, а _k) также приравнивается N.

Доказательство теоремы. Занумеруем составляющие iой категории количествами от 1 по n_i. Элемент из 1 категории разрешено избрать n1 методами. Ежели мы избрали вещество j, 1<=i<= n₁, то избрать вещество из 2-ой категории мы можем n2 методами. Получаем, что с первым составляющей j возможно составить n2 пар (j, l), где 1<=l<= n₂ (рисунок 15).

Рисунок 15. Создание группы, Но столько же пар разрешено составить и с любым иным составляющей 1 категории. Тогда всего пар, в каких 1-ый элемент подобран из 1 категории, а 2-ой — из 2-ой, существует ровно.

Иначе говоря, имеется способов избрать сообразно 1 составляющей из первых 2-ух групп. Возьмем 1 эту пару (j, l). Заметим, что элемент из третьей категории разрешено избрать n3 методами, то имеется возможно собрать ровно n3 троек (j, l, m), добавляя к предоставленной паре (j, l) любой из n3 частей третьей категории.

Но столько же троек разрешено собрать и с любой иной парой (j, l). Тогда всего троек, в каких 1-ый элемент подобран из 1 категории, 2-ой — из 2-ой, а 3-ий — из третьей, существует ровно .

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

Урны и шарики. Имеется урна, (то имеется ящичек), имеющая n занумерованных объектов, которые мы без ограничения общности станем полагать шариками. Мы избираем из данной урны k шариков. Нас интересует, сколькими методами разрешено избрать k шариков из n, либо насколько разных итогов (то имеется комплектов, состоящих из k шариков) выйдет.

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

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

Рассмотрим следующие вероятные схемы выбора:

• 1) Отбор с возвращением: любой выбранный шарик возвращается в урну, то имеется каждый из k шариков выбирается из полной урны. В полученном комплекте, состоящем из k номеров шариков, имеют все шансы пересекаться одни и те же номера (подборка с повторениями).
• 2) Отбор без возвращения: подобранные шарики в урну не возвращаются, и в полученном комплекте не могут пересекаться одни и те же номера (подборка без повторений).

И в первом, и во втором случае итогом выбора является комплект из k номеров шариков. Удобно полагать, что шарики постоянно выбираются последовательно, по 1 (с возвращением либо без).

Условимся, какие итоги мы будем полагать разными.

Имеется ровно 2 возможности:

• 1) Отбор с учетом порядка: 2 комплекта номеров шариков считаются разными, если они различаются составом либо порядком номеров. Так, при выборе 3-х шариков из урны, содержащей 5 шариков, комплекты (1,2,5), (2,5,1) (4,4,5) различны, если делается отбор с учетом распорядка.
• 2) Отбор без учета порядка: 2 комплекта номеров шариков считаются разными, если они различаются составом. Комплекты, имеющие отличия только порядком следования номеров, числятся схожими. Так, в примере выше 1-ые 2 комплекта (1,2,5), (2,5,1) есть один и тот же итог выбора, а комплект (4,4,5) — иной итог выбора.

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

Урновая схема: отбор в отсутствии возвращения, с учетом порядка Теорема. Общее количество выборок в схеме выбора k частей из n без возвращения и с учетом распорядка определяется формулой и именуется числом размещений из n частей по k элементов.

(9).

Доказательство. 1-ый шарик разрешено избрать n методами. При каждом из данных методик 2-ой шарик разрешено избрать n-1 методом, и т. д. Последний k-й шарик разрешено избрать (n-k+1) методом. По теореме 1, общее количество методик выбора равно.

(10).

что и требовалось доказать.

Следствие 1. Количество вероятных перестановок большого количества из n частей есть n!

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

Урновая схема: отбор в отсутствии возвращения и без учета порядка. Общее численность выборок в схеме выбора k частей из n в отсутствии возвращения и без учета порядка определяется формулой (12).

	(12).

и именуется количеством сочетаний из n частей по k частей.

Доказательство. Заметим, что, согласно следствию 1, из всякой подборки данного состава (состоящей из k частей) разрешено сформировать k! выборок, отличающихся друг от друга лишь порядком частей.

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

Урновая схема: отбор с возвращением и с учетом порядка. Общее количество выборок в схеме выбора k частей из n с возвращением и с учетом порядка определяется формулой (13).

Доказательство. 1-ый шарик разрешено избрать n методами. При каждом из данных методик 2-ой шарик разрешено избрать также n методами, и так k раз.

Урновая схема: отбор с возвращением и в отсутствии учета порядка. Рассмотрим урну с 2-мя шариками и перечислим итоги выбора 2-ух шариков из данной урны при выборе с возвращением (таблица 30).

Таблица 30. Таблица выбора 2 шариков.

Заметим, что в схеме «без учета порядка» вышло 3 разных итога в отличие от 4 в схеме «с учетом порядка» (количество 4 появляется и согласно теореме 4); и что никаким делением на «количество каких-нибудь перестановок» количество 3 из 4 заполучить не получится.

Теорема 5. Общее численность выборок в схеме выбора k частей из n с возвращением и без учета распорядка определяется формулой (14).

(14).

Доказательство. Рассмотрим тщательно, чем различаются друг от друга 2 различных итога такой схемы выбора. Нам не важен распорядок номеров, то имеется мы предусматриваем лишь, сколько раз в нашем комплекте из k номеров шариков появился шарик номер 1, шарик номер 2, …, шарик номер n. То имеется итог выбора разрешено представить комплектом количеств k₁, k₂, …k_n, в котором k_i — количество появлений шарика номер i в выборке, и k₁+ k₂+ …+k_n.= k. При этом 2 итога опыта различны, если соответствующие им комплекты k₁, k₂, …, k_n никак не схожи.

Предположим себе другой опыт, имеющий точно такие же итоги (и, следовательно, их столько же). Имеется n ящиков, в которых располагается k шариков. Нас интересует лишь численность шариков в каждом ящике. То имеется, итогом опыта снова является комплект чисел k₁, k₂, …k_n, в котором k_i — количество шариков в ящике с номером i, и k₁+ k₂+ … +k_n.= k. Числа k_i по-прежнему принимают натуральные значения либо равны 0.

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

Мы видим итог размещения 9 шариков по 7 ящикам. Тут 1-й ящик содержит 3 шарика, 2-й и 6-й ящики пусты, 3-й ящик содержит 1 шарик, и в 4-м и 5-м ящиках имеется по 2 шарика. Переложим один шарик из первого ящика во 2-ой и изобразим таким же образом еще один итог размещения:

И еще один:

Видим, что все размещения разрешено получить, изменяя между собой шарики и перегородки, либо расставляя k шариков на n-1+k месте. Количество n-1+k получается так: у n ящиков имеется ровно n+1 перегородка, считая крайние, либо n-1 перегородка, если не считать крайние, которые двигать нельзя. И имеется k шариков. Перебрав все вероятные методы расставить k шариков на этих n-1+k местах (и устанавливая на оставшиеся места перегородки), переберем все нужные размещения.

Но способов расставить k шариков на n-1+k местах ровно — это в точности количество методик избрать из n-1+k номеров мест k номеров мест (в отсутствии учета порядка и в отсутствии возвращения), на которые необходимо поместить шарики. Заметим, что равенство верно как по определению биномиальных коэффициентов или свойствам треугольника Паскаля, так и в силу того, что разрешено вместо выбора k мест для шариков избирать n-1 пространство для перегородок ящиков, заполняя шариками оставшиеся места. [10].