Общие правила комбинаторики

Рассмотрим k множеств М , М , М , …, М , содержащих по m , m , m ,…, m элементов соответственно. Выбирается по одному элементу из каждого множества и составляется еще одно множество. Число способов, которыми можно выбрать по одному элементу из каждого множества, равно произведению m ∙ m ∙ m ∙…∙ m . В этом и состоит основной принцип произведения комбинаторики.

В задачах теории вероятностей часто рассматриваются различные соединения (комбинации) k элементов из множества, содержащего n элементов (k≤n). Будем рассматривать такие соединения, в которые каждый элемент данного множества может входить не более одного раза, то есть соединения без повторений. Рассмотрим три вида соединений: размещения, перестановки, сочетания.

Определение. Размещениями из n элементов по k элементов называются наборы k элементов, отличающиеся один от другого или самими элементами (составом элементов), или их порядком. Число размещений обозначается A .

Число размещений из n элементов по k элементов находится по формуле:

А =n∙(n–1)∙(n–2)∙…∙(n–(k–1)). (1)

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

Перестановки – это частный случай размещений. Число всех перестановок обозначают символом Р . Число Р найти несложно. Для этого в формулу (1) подставляем k=n.

Р =n∙(n–1)∙(n–2)∙…∙(n–(k–1))∙…∙2∙1=n!

Определение. Произведение n первых натуральных чисел называется факториалом числа n и обозначается символом n!(читается «эн факториал»).

Р =1·2·3 …∙n=n! (2)

Приведем некоторые значения факториала:

0!=1, 5!= 1·2·3·4∙5=120,

1!=1, 6!= 1·2·3·4∙5∙6=720,

2!=1·2=2, 7!= 1·2·3·4∙5∙6∙7=5040,

3!=1·2·3=6, 8!= 1·2·3·4∙5∙6∙7∙8=40320,

4!=1·2·3·4=24, 9!= 1·2·3·4∙5∙6∙7∙8∙9=362880.

Определение. Сочетаниями, содержащими k элементов, выбранных из n элементов заданного множества, называются всевозможные наборы k элементов, различающиеся хотя бы одним элементом. Число сочетаний из n элементов по k элементов обозначают С или (.