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

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

Комбинаторные объекты (англ. 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]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]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]P_{n, k} = P_{n, k - 1} + P_{n - k, k}[/math], если [math]k \leqslant n[/math], и [math]P_{n, k} = P_{n, n}[/math], если [math]k \gt n[/math]; где [math]k[/math] — число, не превышаемое слагаемыми, [math]P_{0, 0} = 1[/math], [math]P_{i, 0} = 0[/math] при [math]i \gt 0[/math], причем начальное значение [math]k[/math] — это [math]n[/math]. Данную рекуррентную формулу можно понимать как "[math]n = (k - 1) + (n - k)[/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] непустых подмножеств.

• Применение чисел Стирлинга второго порядка

Источники

• Википедия - Комбинаторика
• Wikipedia - Combinatorics

https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0 неупорядоченные слагаемые