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

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

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

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

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

Правило сложения: если некоторый объект a можно выбрать n1 способами, а объект b можно выбрать n2 способами, причем первые и вторые способы не пересекаются, то любой из объектов (a или b) можно выбрать элементы комбинаторики - student2.ru способами.

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

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

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

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

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

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

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

элементы комбинаторики - student2.ru

где элементы комбинаторики - student2.ru , причем 1!=1, 0!=1.

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

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

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

элементы комбинаторики - student2.ru

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

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

элементы комбинаторики - student2.ru .

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

элементы комбинаторики - student2.ru (правило симметрии),

элементы комбинаторики - student2.ru ,

элементы комбинаторики - student2.ru (правило Паскаля),

элементы комбинаторики - student2.ru .

Наши рекомендации