Комбинаторные объекты — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Согласно правилам русского языка, правильно будет "векторы", а не "вектора")
(не показано 12 промежуточных версий 2 участников)
Строка 1: Строка 1:
  
 
{{Определение
 
{{Определение
|definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}
+
|definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}
  
 
{{Определение
 
{{Определение
|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''упорядоченными'''.
+
|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''упорядоченными''' (англ. ''ordered'').
 
}}
 
}}
  
 
== Примеры комбинаторных объектов ==
 
== Примеры комбинаторных объектов ==
=== Битовые вектора ===
+
=== Битовые векторы ===
'''[[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''' &mdash; последовательность нулей и единиц заданной длины. Количество таких объектов вычисляется по формуле <tex>2^{n}</tex>, так как на каждое из <tex>n</tex> мест мы можем поставить один из двух элементов.
+
{{Определение
 +
|definition='''[[Получение объекта по номеру#Битовые векторы | Битовые векторы]]''' (англ. ''bit vectors'') &mdash; последовательность нулей и единиц заданной длины.
 +
}}
  
 
=== Перестановки ===
 
=== Перестановки ===
'''Перестановки<ref>[http://www.mathelp.spb.ru/book2/tv3.htm/]</ref>''' &mdash; это упорядоченный набор чисел <tex>1, 2,\ldots, n</tex>, обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу <tex>i</tex> ставит соответствие <tex>i</tex>-й элемент из набора. Количество перестановок равно <tex>P_n = n!</tex>. Получить эту формулу можно следующим образом: поставим один из <tex>n</tex> элементов на первое место, далее поставим на второе один из <tex>n - 1</tex> оставшихся элементов,... один из <tex>1</tex> элемента на последнее. Всего таких выборов можно совершить <tex>n \times (n - 1) \times ... \times 1 = n!</tex>.
+
{{Определение
 +
|definition='''Перестановки<ref>[https://ru.wikipedia.org/wiki/%D0%9F%D0%B5%D1%80%D0%B5%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B0 Википедия — Перестановки]</ref>''' (англ. ''permutations'') &mdash; упорядоченный набор чисел <tex>1, 2,\ldots, n</tex>, обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу <tex>i</tex> ставит соответствие <tex>i</tex>-й элемент из набора.
 +
}}
 +
Примером перестановки может служить задача о рассадке <tex>n</tex> человек за стол по <tex>n</tex> местам.
 +
 
 +
=== Перестановки с повторениями ===
 +
{{Определение
 +
|definition='''Перестановки с повторениями''' (англ. ''permutations with repetitions'') — те же перестановки, однако некоторые элементы могут встречаться несколько раз.
 +
}}
 +
В пример можно привести следующую задачу: имеется набор книг <tex>\{a_1, a_2, \ldots, a_n\}</tex>, каждая из которых имеется в <tex>k_1, k_2, \ldots, k_n</tex> экземплярах соответственно. Сколько существует способов переставить книги на полке?
 +
 
 +
=== Размещения ===
 +
{{Определение
 +
|definition='''Размещение'''<ref>[https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%BC%D0%B5%D1%89%D0%B5%D0%BD%D0%B8%D0%B5 Википедия — Размещения]</ref> (англ. ''arrangement'') из <tex>n</tex> по <tex>k</tex> &mdash; упорядоченный набор из <tex>k</tex> различных элементов некоторого <tex>n</tex>-элементного множества.
 +
}}
 +
Примером размещения может служить задача о рассадке <tex>k</tex> человек за стол по <tex>n</tex> местам, где <tex>n > k</tex>.
 +
 
 +
=== Размещения с повторениями ===
 +
{{Определение
 +
|definition='''Размещение с повторениями''' (англ. ''arrangement with repetitions''), составленное из данных <tex>n</tex> элементов по <tex>k</tex> — отображение множества <tex>k</tex> первых натуральных чисел <tex>1, 2, \ldots, k</tex> в данное множество <tex>\{a_1, a_2, \ldots, a_n\}</tex>.
 +
}}
 +
В пример можно привести следующую задачу: имеется <tex>n</tex> книг, каждая в <tex>k</tex> экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?
  
 
=== Сочетания ===
 
=== Сочетания ===
'''Сочетания<ref>[http://www.mathelp.spb.ru/book2/tv3.htm/]</ref>''' из <tex>n</tex> по <tex>k</tex> &mdash; это набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов. Количество таких наборов вычисляется по формуле <tex>C^{k}_n = \frac{n!}{k!(n - k)!}</tex>.  
+
{{Определение
 +
|definition='''Сочетания<ref>[https://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%87%D0%B5%D1%82%D0%B0%D0%BD%D0%B8%D0%B5 Википедия — Сочетания]</ref>''' (англ. ''combinations'') из <tex>n</tex> по <tex>k</tex> &mdash; набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов.
 +
}}
 +
Примером сочетания может служить задача о выборе <tex>k</tex> книг из <tex>n</tex> вариантов.
  
=== Размещения ===
+
=== Сочетания с повторениями ===
* '''Размещение''' из <tex>n</tex> по <tex>k</tex> &mdash; это упорядоченный набор из <tex>k</tex> различных элементов некоторого <tex>n</tex>-элементного множества.
+
{{Определение
 +
|definition='''Сочетания с повторениями''' (англ. ''combinations with repetitions'') — те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.
 +
}}
 +
В пример можно привести следующую задачу: имеется <tex>n</tex> пирожных. Сколько способов купить <tex>k</tex> пирожных?
  
=== Разбиение ===
+
=== Разбиение на неупорядоченные слагаемые ===
* '''Разбиение''' числа '''на неупорядоченные слагаемые''' &mdash; это представление числа <tex>n</tex> в виде суммы слагаемых.
+
{{Определение
 +
|definition=[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''']] (англ. ''partition'') &mdash; представление числа <tex>n</tex> в виде суммы слагаемых.
 +
}}
 +
{{main|Нахождение количества разбиений числа на слагаемые}}
  
=== Разбиение ===
+
=== Разбиение на подмножества ===
* '''Разбиение''' множества <math>X</math> на '''подмножества''' называется семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:
+
{{Определение
 +
|definition=[[Числа Стирлинга второго рода | '''Разбиение''' множества <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>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>X = \bigcup\limits_{\alpha \in A} U_{\alpha}</math>.
 +
}}
 +
{{main|Числа Стирлинга второго рода}}
 +
 +
== Число комбинаторных объектов ==
 +
{| class="wikitable" border = 1
 +
|'''Тип объекта'''||'''Число объектов'''
 +
|-
 +
|Битовые векторы||<tex>2^{n}</tex>
 +
|-
 +
|Перестановки||<tex>P_n = n!</tex>
 +
|-
 +
|Перестановки с повторениями||<tex dpi = "150">\frac{(k_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n!}</tex>
 +
|-
 +
|Размещения||<tex dpi = "150">A^{k}_n = \frac{n!}{(n - k)!}</tex>
 +
|-
 +
|Размещения с повторениями||<tex>n^k</tex>
 +
|-
 +
|Сочетания||<tex dpi = "150">C^{k}_n = \frac{n!}{k!(n - k)!}</tex>
 +
|-
 +
|Сочетания с повторениями||<tex dpi = "150">\widetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex>
 +
|-
 +
|Разбиение на неупорядоченные слагаемые||[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые]]
 +
|-
 +
|Разбиение на подмножества||[[Числа Стирлинга второго рода | Числа Стирлинга второго порядка]]
 +
|}
 +
 +
==Соответствующие доказательства==
 +
{{
 +
Теорема | id=1
 +
|statement=
 +
Число различных битовых векторов длины <tex>n</tex> равно <tex>2^{n}</tex>.
 +
 +
|proof=
 +
Число битовых векторов  {{---}} это частный случай [[#5 | размещения с повторениями]] <tex>2</tex> элементов по <tex>n</tex>. Таким образом, количество различных битовых векторов будет равно <tex>2^n</tex>.
 +
}}
 +
 +
{{
 +
Теорема | id=2
 +
|statement=
 +
Число различных перестановок из <tex>n</tex> элементов равно <tex>P_n = n!</tex>
 +
 +
|proof=
 +
Перестановка {{---}} это частный случай [[#4 | размещения]] <tex>n</tex> элементов по <tex>k</tex> при <tex>k = n</tex>. Таким образом, количество различных перестановок будет равно <tex>n!</tex>
 +
}}
 +
 +
{{
 +
Теорема | id=3
 +
|statement=
 +
Число различных перестановок с повторениями из <tex>k</tex> элементов с <tex>n</tex> группами одинаковых элементов равно <tex>\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!}</tex>, где <tex>k_i</tex> {{---}} это количество одинаковых элементов в <tex>i</tex>{{---}}ой группе.
 +
 +
|proof=
 +
Пусть нужно найти количество перестановок с повторениями на множестве <tex>A</tex> из <tex>k</tex> элементов. Будем учитывать, что в этом множестве <tex>n</tex> групп одинаковых элементов. Количество перестановок из <tex>k</tex> элементов, не учитывая того факта, что элементы могут быть одинаковые, будет равно <tex>k!</tex>.
 +
 +
В каждой итоговой перестановке у нас будет несколько раз учитываться ситуации с одинаковыми элементами ровно столько раз, сколько можно получить перестановок из <tex>k_i</tex>. Таким образом количество перестановок с одинаковым первым элементом будет равно <tex>k_1!</tex>, для второго элемента {{---}} <tex>k_2!</tex>. Общее количество идентичных перестановок будет равно произведению данных факториалов. Итого одинаковых перестановок <tex>k_1! \cdot k_2! \cdot \ldots \cdot k_n!</tex>. Ответом будем являться частное количества всех перестановок и количества одинаковых.
 +
Получаем, что итоговое количество равно <tex>\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!} </tex>
 +
}}
 +
 +
{{
 +
Теорема | id=4
 +
|statement=
 +
Число различных размещений из <tex>n</tex> элементов по <tex>k</tex> равно <tex>A^{k}_n = \frac{n!}{(n - k)!}</tex>
 +
 +
|proof=
 +
 +
Доказательство по индукции. База <tex>k = 1</tex>, тогда количество размещений из <tex>n</tex> по <tex>1</tex> равно <tex>n</tex>.
 +
 +
При <tex>k \geq 2</tex> воспользуемся правилом произведения. Выбрать первый элемент можно <tex>n</tex> различными способами. При каждом первом элементе, все что осталось образует размещение из оставшегося множества, то есть <tex>(n-1)</tex> элементов, по <tex>(k - 1)</tex>. Следовательно получаем рекуррентную формулу <tex>A_{n}^{k}=n \cdot A_{n-1}^{k-1}</tex>. Отсюда получаем <tex>A_{n}^{k} = n \cdot (n-1) \cdot \ldots \cdot (n-k+1) = \frac{n!}{(n-k)!}</tex>
 +
}}
 +
 +
{{
 +
Теорема | id=5
 +
|statement=
 +
Число различных размещений с повторениями из <tex>n</tex> элементов по <tex>k</tex> равно <tex>\overline{A_n^k} = n^k</tex>
 +
 +
|proof=
 +
 +
Докажем по индукции. База: <tex>k = 1</tex>. Тогда <tex> \overline{A_n^1} = n</tex>.
 +
 +
При <tex>k \geq 2</tex> воспользуемся правилом произведения. Выбрать первый элемент можно <tex>n</tex> различными способами. При каждом первом элементе, все что осталось образует размещение с повторениями  из того же самого множества, то есть из n элементов, по <tex>(k - 1)</tex>. Следовательно получаем рекуррентную формулу <tex>\overline{A_n^k} = n \cdot \overline{A_{n}^{k-1}}</tex>. Отсюда получаем <tex>\overline{A_n^k}=n \cdot n \ldots = n^k </tex>
 +
}}
 +
 +
{{
 +
Теорема | id=6
 +
|statement=
 +
Число различных сочетаний из <tex>n</tex> элементов по <tex>k</tex> равно <tex>C^{k}_n = \frac{n!}{k!(n - k)!}</tex>
 +
 +
|proof=
 +
 +
Всего размещений из <tex>n</tex> элементов по <tex>k</tex> равно <tex>A_n^k  = \frac{n!}{(n - k)!}</tex>. В каждом размещении выбраны <tex>k</tex> элементов из данного множества. Если игнорировать порядок этих выбранных <tex>k</tex> элементов, мы получим некоторые сочетания из данного множества по <tex>k</tex>. Другими словами, размещение с одним и тем же набором выбранных <tex>k</tex> элементов задают одно и то же сочетание по <tex>k</tex> элементов.
 +
 +
Так как размещения с одним и тем же набором выбранных <tex>k</tex> элементов различаются только порядком элементов и число различных перестановок из <tex>k</tex> элементов равно <tex>k!</tex>, то итоговая формула будет равна <tex>C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n - k)!}</tex>
 +
}}
 +
 +
{{
 +
Теорема | id=7
 +
|statement=
 +
Число различных сочетаний с повторениями из <tex>n</tex> элементов по <tex>k</tex> равно <tex>\overline{C^k_n} = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex>
 +
 +
|proof=
 +
 +
Рассмотрим двоичный вектор из <tex>(n+k-1)</tex> координат, в котором <tex>(n-1)</tex> нулей и <tex>k</tex> единиц.
  
== Подсчет числа комбинаторных объектов с помощью рекуррентных формул ==
+
Будем считать нули разделителями, которые делят этот вектор на <tex>n</tex> частей.
Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с <tex>n</tex> предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов (одного, двух) решение задачи легко находится.
 
  
'''Количество разбиений числа на неупорядоченные слагаемые'''
+
Тогда предположим, что число единиц в <tex>i</tex>{{---}}м блоке {{---}} это число элементов <tex>k_i</tex> в сочетании с повторением, которое соответствует этому вектору, где <tex>k_i</tex> {{---}} это элемент из изначального множества с номером i.
  
Пусть <tex>n</tex> - число, которое мы разбиваем, а <tex>t</tex> - максимальное слагаемое в разбиении, тогда количество разбиений числа на слагаемые удовлетворяет рекуррентному соотношению:
+
Пример: Если у нас есть набор элементов 1 1 2 2 3, то <tex>k_2</tex> = 2.
  
<tex>A(0, t) = 0</tex>, где <tex>t > 0</tex>,
+
Получаем, что каждому сочетанию с повторениями из <tex>n</tex> по <tex>k</tex> соответствует некоторый вектор из нулей и единиц с <tex>(n+k-1)</tex> координатами, в котором <tex>(n-1)</tex> нулей. Также наоборот, по каждому такому вектору однозначно восстанавливается сочетание с повторением, ему соответствующее. Значит, число сочетаний с повторениями из <tex>n</tex> по <tex>k</tex> совпадает с числом таких векторов.
  
<tex>A(1, 1) = 1</tex>,
+
Таких векторов столько, сколько вариантов выбрать <tex>k</tex> координат, на которых должны стоять единицы из <tex>(n+k-1)</tex>. Таким образом, ответом будет являться число сочетаний из <tex>(n+k-1)</tex> по <tex>k</tex>. Тогда количество равно <tex> \overline{C_n^k} = C_{n+k-1}^{k}</tex>
 +
}}
  
<tex>A(n, t) = A(n, t - 1) + A(n - t, t)</tex>
 
  
'''Количество неупорядоченных разбиений <tex>n</tex>-элементного множества на <tex>k</tex> непустых подмножеств.'''
+
== См. также ==
*[http://neerc.ifmo.ru/wiki/index.php?title=%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%A1%D1%82%D0%B8%D1%80%D0%BB%D0%B8%D0%BD%D0%B3%D0%B0_%D0%B2%D1%82%D0%BE%D1%80%D0%BE%D0%B3%D0%BE_%D1%80%D0%BE%D0%B4%D0%B0#.D0.9F.D1.80.D0.B8.D0.BC.D0.B5.D0.BD.D0.B5.D0.BD.D0.B8.D1.8F Применение чисел Стирлинга второго порядка]
+
*[[Генерация комбинаторных объектов в лексикографическом порядке | Генерация комбинаторных объектов в лексикографическом порядке]]
 +
*[[Получение следующего объекта | Получение следующего объекта]]
 +
*[[Получение номера по объекту | Получение номера по объекту]]
 +
*[[Получение объекта по номеру | Получение объекта по номеру]]
  
== Источники ==
+
== Примечания ==
 
<references/>
 
<references/>
*[http://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BC%D0%B1%D0%B8%D0%BD%D0%B0%D1%82%D0%BE%D1%80%D0%B8%D0%BA%D0%B0 Википедия - Комбинаторика]
+
 
*[http://en.wikipedia.org/wiki/Combinatorics Wikipedia - Combinatorics]
+
== Источники информации ==
 +
* [http://hijos.ru/izuchenie-matematiki/algebra-10-klass/19-razmeshheniya-perestanovki-sochetaniya-s-povtoreniyami-formula-vklyucheniya-isklyucheniya/ Математика, которая мне нравится — Размещения, перестановки, сочетания с повторениями. Формула включения – исключения]
 +
 
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
 
[[Категория: Комбинаторика ]]
 
[[Категория: Комбинаторика ]]
 +
[[Категория: Комбинаторные объекты ]]

Версия 22:34, 11 ноября 2021


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


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


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

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

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


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

Определение:
Перестановки[1] (англ. 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] экземплярах соответственно. Сколько существует способов переставить книги на полке?

Размещения

Определение:
Размещение[2] (англ. 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] экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?

Сочетания

Определение:
Сочетания[3] (англ. 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] — некоторое множество индексов, если:
  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]
Разбиение на неупорядоченные слагаемые Нахождение количества разбиений числа на слагаемые
Разбиение на подмножества Числа Стирлинга второго порядка

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

Теорема:
Число различных битовых векторов длины [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]


См. также

Примечания

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