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

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

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

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

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

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

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

Битовые вектора (англ. bit vectors) — последовательность нулей и единиц заданной длины.

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

Перестановки (англ. permutations) — упорядоченный набор чисел [math]1, 2,\ldots, n[/math], обычно трактуемый как биекция на множестве [math]\{ 1, 2,\ldots, n \}[/math], которая числу [math]i[/math] ставит соответствие [math]i[/math]-й элемент из набора.

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

Перестановки с повторениями (англ. permutations with repetitions) — те же перестановки, однако некоторые элементы могут встречаться несколько раз.

Размещения

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

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

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

Сочетания

Сочетания (англ. combinations) из [math]n[/math] по [math]k[/math] — набор [math]k[/math] элементов, выбранных из данных [math]n[/math] элементов.

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

Сочетания с повторениями (англ. combinations with repetitions) — те же сочетания, только теперь даны [math]n[/math] типов элементов, из которых нужно выбрать [math]k[/math] элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.

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

Разбиение числа на неупорядоченные слагаемые (англ. partition) — представление числа [math]n[/math] в виде суммы слагаемых.

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

Разбиение множества [math]X[/math] на подмножества (англ. partition of a set) — семейство непустых множеств [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]2^{n}[/math]
Перестановки	[math]P_n = n![/math]
Перестановки с повторениями	[math]\frac{(k_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n!}[/math]
Размещения	[math]A^{k}_n = \frac{n!}{(n - k)!}[/math]
Размещения с повторениями	[math]n^k[/math]
Сочетания	[math]C^{k}_n = \frac{n!}{k!(n - k)!}[/math]
Сочетания с повторениями	[math]\widetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}[/math]
Разбиение на неупорядоченные слагаемые	Нахождение количества разбиений числа на слагаемые
Разбиение на подмножества	Числа Стирлинга второго порядка

См. также

• Генерация комбинаторных объектов в лексикографическом порядке
• Получение следующего объекта
• Получение номера по объекту
• Получение объекта по номеру

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

• Математика, которая мне нравится — Размещения, перестановки, сочетания с повторениями. Формула включения – исключения