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

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

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

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

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

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

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

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

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

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

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

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

Примером перестановки может служить задача о рассадке [math]n[/math] человек за стол по [math]n[/math] местам.

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

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

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

В пример можно привести следующую задачу: имеется набор книг [math]\{a_1, a_2, \ldots, a_n\}[/math], каждая из которых имеется в [math]k_1, k_2, \ldots, k_n[/math] экземплярах соответственно. Сколько существует способов переставить книги на полке?

Размещения

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

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

Примером размещения может служить задача о рассадке [math]k[/math] человек за стол по [math]n[/math] местам, где [math]n \gt k[/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].

В пример можно привести следующую задачу: имеется [math]n[/math] книг, каждая в [math]k[/math] экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?

Сочетания

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

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

Примером сочетания может служить задача о выборе [math]k[/math] книг из [math]n[/math] вариантов.

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

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

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

В пример можно привести следующую задачу: имеется [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] — некоторое множество индексов, если: [math]U_{\alpha} \cap U_{\beta} = \emptyset[/math] для любых [math]\alpha, \beta \in A[/math], таких что [math]\alpha \not= \beta[/math]; [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]
Разбиение на неупорядоченные слагаемые	Нахождение количества разбиений числа на слагаемые
Разбиение на подмножества	Числа Стирлинга второго порядка

Соответствующие доказательства

Теорема:

Число различных битовых векторов длины [math]n[/math] равно [math]2^{n}[/math].

Доказательство:

[math]\triangleright[/math]

Число битовых векторов — это частный случай размещения с повторениями [math]2[/math] элементов по [math]n[/math]. Таким образом, количество различных битовых векторов будет равно [math]2^n[/math].

[math]\triangleleft[/math]

Теорема:

Число различных перестановок из [math]n[/math] элементов равно [math]P_n = n![/math]

Доказательство:

[math]\triangleright[/math]

Перестановка — это частный случай размещения [math]n[/math] элементов по [math]k[/math] при [math]k = n[/math]. Таким образом, количество различных перестановок будет равно [math]n![/math]

[math]\triangleleft[/math]

Теорема:

Число различных перестановок с повторениями из [math]k[/math] элементов с [math]n[/math] группами одинаковых элементов равно [math]\overline{P_k} (k_1, k_2, \ldots, k_n) = \frac{(k_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n!}[/math], где [math]k_i[/math] — это количество одинаковых элементов в [math]i[/math]—ой группе.

Доказательство:

[math]\triangleright[/math]

Пусть нужно найти количество перестановок с повторениями на множестве [math]A[/math] из [math]k[/math] элементов. Будем учитывать, что в этом множестве [math]n[/math] групп одинаковых элементов. Количество перестановок из [math]k[/math] элементов, не учитывая того факта, что элементы могут быть одинаковые, будет равно [math]k![/math]. В каждой итоговой перестановке у нас будет несколько раз учитываться ситуации с одинаковыми элементами ровно столько раз, сколько можно получить перестановок из [math]k_i[/math]. Таким образом количество перестановок с одинаковым первым элементом будет равно [math]k_1![/math], для второго элемента — [math]k_2![/math]. Общее количество идентичных перестановок будет равно произведению данных факториалов. Итого одинаковых перестановок [math]k_1! \cdot k_2! \cdot \ldots \cdot k_n![/math]. Ответом будем являться частное количества всех перестановок и количества одинаковых. Получаем, что итоговое количество равно [math]\frac{k!}{k_1! \cdot k_2! \cdot \ldots \cdot k_n!} = \frac{(k_1 + k_2 + \ldots + k_n)!}{k_1! \cdot k_2! \cdot \ldots \cdot k_n!} [/math]

[math]\triangleleft[/math]

Теорема:

Число различных размещений из [math]n[/math] элементов по [math]k[/math] равно [math]A^{k}_n = \frac{n!}{(n - k)!}[/math]

Доказательство:

[math]\triangleright[/math]

Доказательство по индукции. База [math]k = 1[/math], тогда количество размещений из [math]n[/math] по [math]1[/math] равно [math]n[/math]. При [math]k \geq 2[/math] воспользуемся правилом произведения. Выбрать первый элемент можно [math]n[/math] различными способами. При каждом первом элементе, все что осталось образует размещение из оставшегося множества, то есть [math](n-1)[/math] элементов, по [math](k - 1)[/math]. Следовательно получаем рекуррентную формулу [math]A_{n}^{k}=n \cdot A_{n-1}^{k-1}[/math]. Отсюда получаем [math]A_{n}^{k} = n \cdot (n-1) \cdot \ldots \cdot (n-k+1) = \frac{n!}{(n-k)!}[/math]

[math]\triangleleft[/math]

Теорема:

Число различных размещений с повторениями из [math]n[/math] элементов по [math]k[/math] равно [math]\overline{A_n^k} = n^k[/math]

Доказательство:

[math]\triangleright[/math]

Докажем по индукции. База: [math]k = 1[/math]. Тогда [math] \overline{A_n^1} = n[/math]. При [math]k \geq 2[/math] воспользуемся правилом произведения. Выбрать первый элемент можно [math]n[/math] различными способами. При каждом первом элементе, все что осталось образует размещение с повторениями из того же самого множества, то есть из n элементов, по [math](k - 1)[/math]. Следовательно получаем рекуррентную формулу [math]\overline{A_n^k} = n \cdot \overline{A_{n}^{k-1}}[/math]. Отсюда получаем [math]\overline{A_n^k}=n \cdot n \ldots = n^k [/math]

[math]\triangleleft[/math]

Теорема:

Число различных сочетаний из [math]n[/math] элементов по [math]k[/math] равно [math]C^{k}_n = \frac{n!}{k!(n - k)!}[/math]

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Теорема:

Число различных сочетаний с повторениями из [math]n[/math] элементов по [math]k[/math] равно [math]\overline{C^k_n} = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}[/math]

Доказательство:

[math]\triangleright[/math]

Рассмотрим двоичный вектор из [math](n+k-1)[/math] координат, в котором [math](n-1)[/math] нулей и [math]k[/math] единиц. Будем считать нули разделителями, которые делят этот вектор на [math]n[/math] частей. Тогда предположим, что число единиц в [math]i[/math]—м блоке — это число элементов [math]k_i[/math] в сочетании с повторением, которое соответствует этому вектору, где [math]k_i[/math] — это элемент из изначального множества с номером i. Пример: Если у нас есть набор элементов 1 1 2 2 3, то [math]k_2[/math] = 2. Получаем, что каждому сочетанию с повторениями из [math]n[/math] по [math]k[/math] соответствует некоторый вектор из нулей и единиц с [math](n+k-1)[/math] координатами, в котором [math](n-1)[/math] нулей. Также наоборот, по каждому такому вектору однозначно восстанавливается сочетание с повторением, ему соответствующее. Значит, число сочетаний с повторениями из [math]n[/math] по [math]k[/math] совпадает с числом таких векторов. Таких векторов столько, сколько вариантов выбрать [math]k[/math] координат, на которых должны стоять единицы из [math](n+k-1)[/math]. Таким образом, ответом будет являться число сочетаний из [math](n+k-1)[/math] по [math]k[/math]. Тогда количество равно [math] \overline{C_n^k} = C_{n+k-1}^{k}[/math]

[math]\triangleleft[/math]

См. также

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

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

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