Изменения
added proofs
{{Определение
|definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}
{{Определение
|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''Комбинаторные объектыупорядоченными''' (англ. ''(combinatorial objects)ordered'' — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п).}}
== Примеры комбинаторных объектов ==
# <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=Перестановка {{---}} это частный случай [[#4 | размещения]] <tex>n</tex> элементов по <tex>k</tex>A(0, t) при <tex>k = 0n</tex>. Таким образом, где количество различных перестановок будет равно <tex>t > 0n!</tex>,}}
{{Теорема | id=3|statement=Число различных перестановок с повторениями из <tex>Ak</tex> элементов с <tex>n</tex> группами одинаковых элементов равно <tex>\overline{P_k} (1k_1, k_2, \ldots, 1k_n) = 1\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> элементов, t) = A(nне учитывая того факта, t - 1) + A(n - tчто элементы могут быть одинаковые, t)будет равно <tex>k!</tex>.
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]
[[Категория: Комбинаторные объекты ]]