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

Принцип произведения комбинаций n1n1 n2n2 … nknk … Комбинация элементов n 1 n 2 n k 12 k ШАГИ N = n 1 n 2 … n k

Принцип произведения комбинаций Пусть имеется k групп элементов, причем i -я группа содержит n i элементов, 1 i k. Выберем из каждой группы по одному элементу.Тогда общее число N способов, которыми можно произвести такой выбор, равняется N = n 1 n 2 … n k

Виды комбинаций Перестановки Размещения Сочетания

Перестановки: комбинации (соединения) из одних и тех же элементов, отличающиеся порядком N 123N…

Подсчитаем число перестановок. Используем принцип произведения комбинаций:

Размещения из N элементов по m элементов – упорядоченные подмножества из m элементов, отличающиеся как составом, так и порядком следования элементов m N

Сочетания из N элементов по m элементов – неупорядоченные подмножества из m элементов, отличающиеся только составом элементов. Если в каждом сочетании произвести все возможные m ! перестановок, то мы получим все размещения. Число размещений и число сочетаний Связаны соотношением: Отсюда имеем:

Основное свойство сочетаний Образование сочетаний связано с задачей разбиения множества N элементов на два подмножества так, что одно из них содержит m элементов, а другое – оставшиеся (N-m) элементов и является простейшим случаем более общей задачи о разбиении множества на k неупорядоченных подмножеств, содержащих n 1, n 2, …, n k элементов, причем n 1 + n 2 + … + n k = N. Число таких комбинаций равно

«Урновые» схемы проведения случайных экспериментов Урна (ящик), содержит N пронумерованных шаров Выбор с возвращением Выбор без возвращения Без учета порядка С учетом порядка Вытаскиваем m шаров

Выбор без возвращения с учетом порядка Выбор без возвращения без учета порядка

Выбор с возвращением с учетом порядка Общее количество выборок : m раз Выбор с возвращением без учета порядка Два из двух