Читайте также:
|
Комбинаторика изучает количества комбинаций, подчиненных определенным условиям, которые можно составить из элементов, безразлично какой природы, заданного конечного множества. При непосредственном вычислении вероятностей часто используют формулы комбинаторики. Приведем наиболее употребительные из них.
Перестановками называют комбинации, состоящие из одних и тех же n различных элементов и отличающиеся только порядком их расположения. Число всех возможных перестановок Pn = n!, где n! = 1 * 2 * 3... n.
Заметим, что удобно рассматривать 0!, полагая, по определению, 0! = 1.
Размещениями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются либо составом элементов, либо их порядком. Число всех возможных размещений Amn = n (n - 1)(n - 2)... (n - m + 1).
Сочетаниями называют комбинации, составленные из n различных элементов по m элементов, которые отличаются хотя бы одним элементом. Число сочетаний
С mn = n! / (m! (n - m)!).
Подчеркнем, что числа размещений, перестановок и сочетаний связаны равенством Amn = PmC mn.
З а м е ч а н и е. Выше предполагалось, что все n элементов различны. Если же некоторые элементы повторяются, то в этом случае комбинации с повторениями вычисляют по другим формулам. Например, если среди n элементов есть n1 элементов одного вида, n2 элементов другого вида и т.д., то число перестановок с повторениями Pn (n1,n2,...)= n!/(n1! n2!...), где n1 + n2 +... = n.
При решении задач комбинаторики используют следующие правила:
П р а в и л о с у м м ы. Если некоторый объект А может быть выбран из совокупности объектов m способами, а другой объект В может быть выбран n способами, то выбрать либо А, либо В можно m + n способами.
П р а в и л о п р о и з в е д е н и я. Если объект А можно выбрать из совокупности объектов m способами и после каждого такого выбора объект В можно выбрать n способами, то пара объектов (А, В) в указанном порядке может быть выбрана mn способами.
Урновая схема: выбор без возвращения, с учетом порядка
Теорема 2. Общее количество выборок в схеме выбора k элементов из n без возвращения и с учетом порядка определяется формулой и называется числом размещений из n элементов по k элементов.
Доказательство. Первый шарик можно выбрать n способами. При каждом из этих способов второй шарик можно выбрать n-1 способом, и т.д. Последний k-й шарик можно выбрать (n-k+1) способом. По теореме 1, общее число способов выбора равно 
что и требовалось доказать.
Следствие 1. Число возможных перестановок множества из n элементов есть n! 
Доказательство очевидно, если заметить, что перестановка есть не что иное, как результат выбора без возвращения и с учетом порядка всех n элементов из n. Так что общее число перестановок равно
Урновая схема: выбор без возвращения и без учета порядка
Теорема 3. Общее количество выборок в схеме выбора k элементов из n без возвращения и без учета порядка определяется формулой 
и называется числом сочетаний из n элементов по k элементов.
Доказательство. Заметим, что, согласно следствию 1, из каждой выборки данного состава (состоящей из k элементов) можно образовать k! выборок, отличающихся друг от друга только порядком элементов.
То есть число выборок, различающихся еще и порядком, в k! раз больше, чем число выборок, различающихся только составом. Поделив 
k!, получим утверждение теоремы.
Урновая схема: выбор с возвращением и с учетом порядка 
Теорема 4. Общее количество выборок в схеме выбора k элементов из n с возвращением и с учетом порядка определяется формулой
Доказательство. Первый шарик можно выбрать n способами. При каждом из этих способов второй шарик можно выбрать также n способами, и так k раз.
Урновая схема: выбор с возвращением и без учета порядка
Рассмотрим урну с двумя шариками и перечислим результаты выбора двух шариков из этой урны при выборе с возвращением:
С учетом порядка Без учета порядка
(1, 1) (1, 1)
(2, 2) (2, 2)
(1, 2) (1, 2)
(2, 1)
Заметим, что в схеме «без учета порядка» получилось 3 различных результата в отличие от четырех в схеме «с учетом порядка». (число 4 возникает и согласно теореме 4); и что никаким делением на «число каких-нибудь перестановок» число 3 из 4 получить не удастся.
Теорема 5. Общее количество выборок в схеме выбора k элементов из n с возвращением и без учета порядка определяется формулой
Доказательство. Рассмотрим подробно, чем отличаются друг от друга два разных результата такой схемы выбора. Нам не важен порядок номеров, то есть мы учитываем только, сколько раз в нашем наборе из k номеров шариков появился шарик номер 1, шарик номер 2, …, шарик номер n. То есть результат выбора можно представить набором чисел k1, k2, …kn, в котором ki — число появлений шарика номер i в выборке, и k1+ k2+ …+kn.= k. При этом два результата эксперимента различны, если соответствующие им наборы k1, k2, …,kn не совпадают.
Представим себе другой эксперимент, имеющий точно такие же результаты (и, следовательно, их столько же). Есть n ящиков, в которых размещается k шариков. Нас интересует только количество шариков в каждом ящике. То есть, результатом эксперимента снова является набор чисел k1, k2, …kn, в котором ki — число шариков в ящике с номером i, и k1+ k2+ … +kn.= k. Числа ki по-прежнему принимают натуральные значения или равны 0.
А теперь изобразим результат такого размещения в виде схемы, в которой вертикальные линии обозначают перегородки между ящиками, а кружки — находящиеся в ящиках шарики:
Мы видим результат размещения 9 шариков по 7 ящикам. Здесь 1-й ящик содержит 3 шарика, 2-й и 6-й ящики пусты, 3-й ящик содержит 1 шарик, и в 4-м и 5-м ящиках есть по 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 место для перегородок ящиков, заполняя шариками оставшиеся места.
Дата добавления: 2015-01-12; просмотров: 164 | Поможем написать вашу работу | Нарушение авторских прав |