Основные комбинаторные конфигурации

Набор элементов x_i1,…, x_ik из множества X={x₁, …, x_n} называется выборкойобъема k из n элементов или, иначе, (n, k)-выборкой.

Выборка называется упорядоченной, если задан порядок следования элементов в ней. Две упорядоченные выборки, различающиеся лишь порядком следования элементов, считаются различными. Если порядок следования элементов в выборке не является существенным, то такая выборка называется неупорядоченной.

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

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

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

Сочетанием без повторений из n по k называется неупорядоченный набор k элементов, выбранных из данных n элементов (неупорядоченная (n, k)-выборка без возвращения). Наборы, отличающиеся только порядком следования элементов (но не составом), считаются одинаковыми, этим сочетания отличаются от размещений.

Количество всех различных сочетаний (без повторений) из nэлементов по kобозначают или :

Пример

Пусть C = {a, b, c, d}