Комбинаторные объекты

Определение:

Комбинаторные объекты (англ. combinatorial objects) — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.

Определение:

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

Примеры комбинаторных объектов

Битовые вектора

Битовые вектора — последовательность нулей и единиц заданной длины. Количество таких объектов вычисляется по формуле [math]2^{n}[/math], так как на каждое из [math]n[/math] мест мы можем поставить один из двух элементов.

Перестановки

Перестановки — это упорядоченный набор чисел [math]1, 2,\ldots, n[/math], обычно трактуемый как биекция на множестве [math]\{ 1, 2,\ldots, n \}[/math], которая числу [math]i[/math] ставит соответствие [math]i[/math]-й элемент из набора. Количество перестановок равно [math]P_n = n![/math]. Получить эту формулу можно следующим образом: поставим один из [math]n[/math] элементов на первое место, далее поставим на второе один из [math]n - 1[/math] оставшихся элементов,... один из [math]1[/math] элемента на последнее. Всего таких выборов можно совершить [math]n \times (n - 1) \times ... \times 1 = n![/math].

Перестановки с повторениями

Перестановки с повторениями — это те же перестановки, однако некоторые элементы могут встречаться несколько раз. Число различных перестановок с повторениями из элементов [math]{a_1, a_2, ..., a_n}[/math], в которых эти элементы повторяются соответственно [math]k_1, k_2, ..., k_n[/math] раз, равно [math]\frac{(k_1 + k_2 + ... + k_n)!}{k_1!k_2!...k_n!}[/math]. Выведем формулу. Всего перестановок [math](k_1 + k_2 + ... + k_n)![/math], однако среди них есть и повторяющиеся. Такие попадаются, когда мы переставляем местами одинаковые элементы. Тогда всего повторяющихся перестановок будет в [math]k_1!k_2!...k_n![/math] раз. В итоге получаем необходимую формулу.

Размещения

Размещение из [math]n[/math] по [math]k[/math] — это упорядоченный набор из [math]k[/math] различных элементов некоторого [math]n[/math]-элементного множества. Таких наборов [math]A^{k}_n = \frac{n!}{(n - k)!}[/math]. Выведем формулу подобно тому, как выводили для перестановок: на первое место можно поставить один из [math]n[/math] элементов, на следующее один из [math]n - 1[/math],... и на последнее один из [math]n - k + 1[/math]. Всего получится [math]n \times (n - 1) \times ... \times (n - k + 1) = \frac{n!}{(n - k)!}[/math].

Размещения с повторениями

Размещение с повторениями, составленное из данных [math]n[/math] элементов по [math]k[/math] — это отображение множества [math]k[/math] первых натуральных чисел [math]1, 2, ..., k[/math] в данное множество [math]\{a_1, a_2, ..., a_n\}[/math]. Всего таких элементов [math]n^k[/math]. Формула выводится так же, как и для битовых векторов.

Сочетания

Сочетания из [math]n[/math] по [math]k[/math] — это набор [math]k[/math] элементов, выбранных из данных [math]n[/math] элементов. Количество таких наборов вычисляется по формуле [math]C^{k}_n = \frac{n!}{k!(n - k)!}[/math]. Выведем данную формулу из формулы размещений, а именно заметим, что в размещениях порядок элементов имеет значение, а в сочетаниях нет. Это значит, что наборы [math]\{1, 2\}[/math] и [math]\{2, 1\}[/math] эквивалентны. То есть в размещениях любой вариант сочетания повторяется столько же раз, сколько можно сделать перестановок для [math]k[/math] мест. Тогда [math]C^{k}_n = \frac{A^{k}_n}{k!} = \frac{n!}{k!(n - k)!}[/math].

Сочетания с повторениями

Сочетания с повторениями — это те же сочетания, только теперь даны [math]n[/math] типов элементов, из которых нужно выбрать [math]k[/math] элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом. Способов таких выборов всего [math]\widetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}[/math]. Чтобы вывести формулу, давайте различные элементы в перестановке разделим перегородками, а каждый элемент назовем [math]1[/math], тогда, чтобы получить новую перестановку просто будем менять местами перегородки и [math]1[/math], причем таких перегородок будет [math]n - 1[/math], даже если мы не брали некоторые типы элементов. Таких перестановок [math](n - 1 + k)![/math], а за вычетом перестановок одинаковых элементов (перегородок и [math]1[/math]), коих в [math]k!(n - 1)![/math] раз больше необходимых, получаем необходимую формулу.

Разбиение на неупорядоченные слагаемые

Разбиение числа на неупорядоченные слагаемые — это представление числа [math]n[/math] в виде суммы слагаемых. Всего таких разбиений:

[math]P_{n,k} = \left \{ \begin{array}{ll} P_{n,k - 1} + P_{n - k, k}, & 0 \lt k \leqslant n \\ P_{n, n}, & k \gt n \\ 1, & n = 0, k = 0 \\ 0, & n \neq 0 , k = 0, \end{array} \right.[/math]

где [math]k[/math] — число, не превышаемое слагаемыми, причем начальное значение [math]k = n[/math]. Вывод формулы можно найти здесь.

Разбиение на подмножества

Разбиение множества [math]X[/math] на подмножества — это семейство непустых множеств [math]\{U_{\alpha}\},{\alpha \in A}[/math], где [math]A[/math] — некоторое множество индексов, если:

1. [math]U_{\alpha} \cap U_{\beta} = \emptyset[/math] для любых [math]\alpha, \beta \in A[/math], таких что [math]\alpha \not= \beta[/math];
2. [math]X = \bigcup\limits_{\alpha \in A} U_{\alpha}[/math].

Если задано множество из [math]n[/math] элементов, которое необходимо разбить на [math]k[/math] непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть ([math]\lbrace{n-1\atop k-1}\rbrace[/math] способами), либо поместить его в некоторое подмножество ([math]k[/math][math]\lbrace{n-1\atop k}\rbrace[/math] способами, поскольку каждый из [math]\lbrace{n-1\atop k}\rbrace[/math] способов распределения первых [math]n-1[/math] элементов по [math]k[/math] непустым частям дает [math]k[/math] подмножеств, с которыми можно объединить последний элемент).

[math]\begin{Bmatrix} n \\ k \end{Bmatrix} = \begin{cases} k\begin{Bmatrix} n-1 \\ k \end{Bmatrix} + \begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}, 0\lt k\lt n \\ 0, k = 0 \\ 0, n = 0 \\ 0, k \gt n \\ 1, k = n \end{cases} [/math]

Подробнее можно прочитать на странице о числах Стирлинга второго порядка.

Источники информации

• Размещения, перестановки, сочетания с повторениями