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

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

Многие комбинаторные задачи могут быть решены с помощью двух правил – правила умножения и правила сложения.

Правило умножения: если из некоторого конечного множества первыйобъект (элемент a) можно выбрать n₁ способами, а второй объект (элемент b) – n₂ способами, то оба объекта (a и b) в указанном порядке можно выбрать способами.

Этот принцип распространяется на случай трех и более объектов.

Правило сложения: если некоторый объект a можно выбрать n₁ способами, а объект b можно выбрать n₂ способами, причем первые и вторые способы не пересекаются, то любой из объектов (a или b) можно выбрать способами.

Это правило распространяется на любое конечное число объектов.

Существуют две схемы выбора m элементов из заданного множества: без возвращения, когда выбранные элементы не возвращаются в исходное множество, и с возвращением, когда выбор осуществляется поэлементно с обязательным возвращение отобранного элемента на каждом шаге.

Схема выбора без возвращений

Пусть дано множество, состоящее из n различных элементов.

Размещением из n элементов по k элементов (0≤k≤n) называется любое упорядоченное подмножество данного множества, содержащее k элементов.

Два размещения различны, если они отличаются друг от друга либо составом элементов, либо порядком их расположения.

Число размещений из n элементов по k обозначаются символом и вычисляется по формуле

где , причем 1!=1, 0!=1.

Перестановкой из n элементов называется размещение из n элементов по n элементов.

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

Число перестановок из n элементов обозначается символом и вычисляется по формуле

Сочетанием из n элементов по k (0≤k≤n) называется любое подмножество данного множества, которое содержит k элементов.

Любые два сочетания отличаются друг от друга хотя бы одним элементом (т.е. отличаются только составом элементов). Число сочетаний из n элементов по k обозначается символом и вычисляется по формуле

.

Для чисел (они называются биномиальными коэффициентами) справедливы следующие тождества:

(правило симметрии),

,

(правило Паскаля),

.