Изменения

== {{Определение |definition =='''Комбинаторные объекты''' - это (англ. ''combinatorial objects'') — конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}} {{Определение|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''упорядоченными''' (англ. ''ordered'').}}

1) === Битовые векторы ==={{Определение|definition='''[[Получение объекта по номеру#Битовые векторавекторы | Битовые векторы]]''' - (англ. ''bit vectors'') &mdash; последовательность нулей и единиц заданной длины.}} === Перестановки ==={{Определение|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>.

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

3) '''Сочетания''' {{Теорема | id=6|statement=Число различных сочетаний из ''<tex>n'' </tex> элементов по ''<tex>k</tex> равно <tex>C^{k}_n = \frac{n!}{k'' !(n - это набор ''k'' элементов, выбранных из данных ''n'' элементов.)!}</tex>

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>}}

{{Теорема | 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</tex> частей.

Тогда предположим, что число единиц в <tex>A(0, t) = 0i</tex>{{---}}м блоке {{---}} это число элементов <tex>k_i</tex>в сочетании с повторением, которое соответствует этому вектору, где ''t'' <tex>k_i</tex> 0,{{---}} это элемент из изначального множества с номером i.

Пример: Если у нас есть набор элементов 1 1 2 2 3, то <tex>A(1, 1) = 1k_2</tex>,= 2.

Получаем, что каждому сочетанию с повторениями из <tex>A(n, t) = A</tex> по <tex>k</tex> соответствует некоторый вектор из нулей и единиц с <tex>(n, t +k- 1) + A</tex> координатами, в котором <tex>(n - t, t1)</tex>нулей. Также наоборот, где первый параметр - это числопо каждому такому вектору однозначно восстанавливается сочетание с повторением, которое мы разбиваемему соответствующее. Значит, а второй - это максимальное слагаемое в разбиениичисло сочетаний с повторениями из <tex>n</tex> по <tex>k</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>S(n, n) = 1</tex>, для ''n'' ≥ 0,= См. также ==*[[Генерация комбинаторных объектов в лексикографическом порядке | Генерация комбинаторных объектов в лексикографическом порядке]]*[[Получение следующего объекта | Получение следующего объекта]]*[[Получение номера по объекту | Получение номера по объекту]]*[[Получение объекта по номеру | Получение объекта по номеру]]

<tex>S(n, 0) = 0= Примечания ==<references/tex>, для ''n'' > 0,

<tex>S(n, k) = S(n = Источники информации ==* [http://hijos.ru/izuchenie-matematiki/algebra- 1, k 10-klass/19-razmeshheniya-perestanovki-sochetaniya-s-povtoreniyami-formula- 1) + k \cdot S(n vklyucheniya- 1isklyucheniya/ Математика, k)</tex> для 0 < ''k'' < ''n''которая мне нравится — Размещения, перестановки, сочетания с повторениями.Формула включения – исключения]

== Источники ==[[Категория: Дискретная математика и алгоритмы]][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 Комбинаторика - Википедиа]][[Категория: Комбинаторные объекты ]]