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

Материал из Викиконспекты
Перейти к: навигация, поиск
(added proofs)
(не показано 25 промежуточных версий 7 участников)
Строка 1: Строка 1:
== Определение ==
+
 
'''Комбинаторные объекты''' — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.
+
{{Определение
 +
|definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}
 +
 
 +
{{Определение
 +
|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''упорядоченными''' (англ. ''ordered'').
 +
}}
  
 
== Примеры комбинаторных объектов ==
 
== Примеры комбинаторных объектов ==
1) '''Битовые вектора''' — последовательность нулей и единиц заданной длины.
+
=== Битовые вектора ===
 +
{{Определение
 +
|definition='''[[Получение объекта по номеру#Битовые вектора | Битовые вектора]]''' (англ. ''bit vectors'') — последовательность нулей и единиц заданной длины.
 +
}}
 +
 
 +
=== Перестановки ===
 +
{{Определение
 +
|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> экземплярах. Сколькими способами может быть сделан выбор книг из числа данных?
 +
 
 +
=== Сочетания ===
 +
{{Определение
 +
|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> вариантов.
 +
 
 +
=== Сочетания с повторениями ===
 +
{{Определение
 +
|definition='''Сочетания с повторениями''' (англ. ''combinations with repetitions'') — те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.
 +
}}
 +
В пример можно привести следующую задачу: имеется <tex>n</tex> пирожных. Сколько способов купить <tex>k</tex> пирожных?
 +
 
 +
=== Разбиение на неупорядоченные слагаемые ===
 +
{{Определение
 +
|definition=[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''']] (англ. ''partition'') &mdash; представление числа <tex>n</tex> в виде суммы слагаемых.
 +
}}
 +
{{main|Нахождение количества разбиений числа на слагаемые}}
 +
 
 +
=== Разбиение на подмножества ===
 +
{{Определение
 +
|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>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>.
  
2) '''Перестановки''' &mdash; это упорядоченный набор чисел <tex>1, 2,\ldots, n,</tex> обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу ''i'' ставит соответствие ''i''-й элемент из набора.
+
При <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>
 +
}}
  
3) '''Сочетания''' из ''n'' по ''k'' &mdash; это набор ''k'' элементов, выбранных из данных ''n'' элементов.
+
{{
 +
Теорема | id=6
 +
|statement=
 +
Число различных сочетаний из <tex>n</tex> элементов по <tex>k</tex> равно <tex>C^{k}_n = \frac{n!}{k!(n - k)!}</tex>
  
4) '''Размещение''' из ''n'' по ''k'' &mdash; это упорядоченный набор из ''k'' различных элементов некоторого n-элементного множества.
+
|proof=
  
5) '''Разбиение''' числа '''на слагаемые'''.
+
Всего размещений из <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> элементов.
  
6) Все возможные подмножества заданного множества.
+
Так как размещения с одним и тем же набором выбранных <tex>k</tex> элементов различаются только порядком элементов и число различных перестановок из <tex>k</tex> элементов равно <tex>k!</tex>, то итоговая формула будет равна <tex>C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n - k)!}</tex>
 +
}}
  
7) '''Разбиение''' множества '''на подмножества''' такие, что в объединении они дают исходное множество, но при этом ни одно из них не пересекается с любым другим.
+
{{
 +
Теорема | 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=
Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с ''n'' предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов (одного, двух) решение задачи легко находится.
 
  
'''Количество разбиений числа на слагаемые'''
+
Рассмотрим двоичный вектор из <tex>(n+k-1)</tex> координат, в котором <tex>(n-1)</tex> нулей и <tex>k</tex> единиц.
  
Количество разбиений числа на слагаемые удовлетворяют рекуррентному соотношению:
+
Будем считать нули разделителями, которые делят этот вектор на <tex>n</tex> частей.
  
<tex>A(0, t) = 0</tex>, где ''t'' > 0,
+
Тогда предположим, что число единиц в <tex>i</tex>{{---}}м блоке {{---}} это число элементов <tex>k_i</tex> в сочетании с повторением, которое соответствует этому вектору, где <tex>k_i</tex> {{---}} это элемент из изначального множества с номером i.
  
<tex>A(1, 1) = 1</tex>,
+
Пример: Если у нас есть набор элементов 1 1 2 2 3, то <tex>k_2</tex> = 2.
  
<tex>A(n, t) = A(n, t - 1) + A(n - t, t)</tex>, где первый параметр - это число, которое мы разбиваем, а второй - это максимальное слагаемое в разбиении.
+
Получаем, что каждому сочетанию с повторениями из <tex>n</tex> по <tex>k</tex> соответствует некоторый вектор из нулей и единиц с <tex>(n+k-1)</tex> координатами, в котором <tex>(n-1)</tex> нулей. Также наоборот, по каждому такому вектору однозначно восстанавливается сочетание с повторением, ему соответствующее. Значит, число сочетаний с повторениями из <tex>n</tex> по <tex>k</tex> совпадает с числом таких векторов.  
  
'''Количество неупорядоченных разбиений ''n''-элементного множества на ''k'' непустых подмножеств.'''
+
Таких векторов столько, сколько вариантов выбрать <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>S(n, n) = 1</tex>, для ''n'' ≥ 0,
+
== См. также ==
 +
*[[Генерация комбинаторных объектов в лексикографическом порядке | Генерация комбинаторных объектов в лексикографическом порядке]]
 +
*[[Получение следующего объекта | Получение следующего объекта]]
 +
*[[Получение номера по объекту | Получение номера по объекту]]
 +
*[[Получение объекта по номеру | Получение объекта по номеру]]
  
<tex>S(n, 0) = 0</tex>, для ''n'' > 0,
+
== Примечания ==
 +
<references/>
  
<tex>S(n, k) = S(n - 1, k - 1) + k \cdot S(n - 1, k)</tex> для 0 < ''k'' < ''n''.
+
== Источники информации ==
 +
* [http://hijos.ru/izuchenie-matematiki/algebra-10-klass/19-razmeshheniya-perestanovki-sochetaniya-s-povtoreniyami-formula-vklyucheniya-isklyucheniya/ Математика, которая мне нравится — Размещения, перестановки, сочетания с повторениями. Формула включения – исключения]
  
== Источники ==
+
[[Категория: Дискретная математика и алгоритмы]]
[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 Комбинаторика - Википедиа]
+
[[Категория: Комбинаторика ]]
 +
[[Категория: Комбинаторные объекты ]]

Версия 13:44, 8 января 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]


См. также

Примечания

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