Изменения

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

|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''Упорядоченным множествомупорядоченными''' называется множество, на элементах которого установлено отношение, обладающее следующими свойствами:1(англ. Для любых двух элементов <tex>a</tex> и <tex>b</tex> данного множества существует только одно из следующих соотношений: <tex>a < b, ~a > b, ~a = b</tex>2''ordered''). Для любых трех элементов данного множества <tex>a, b, c</tex>: <tex>~(a < b</tex> & <tex>b < c) => a < c</tex>

* === Битовые векторы ==={{Определение|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=''n'Размещение''' по <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> (англ. ''karrangement'' ) из <tex>n</tex> по <tex>k</tex> &mdash; это упорядоченный набор из <tex>k</tex> различных элементов некоторого <tex>n</tex>-элементного множества.}}Примером размещения может служить задача о рассадке <tex>k</tex> человек за стол по <tex>n</tex> местам, где <tex>n > k</tex>. === Размещения с повторениями ==={{Определение|definition=''k'Размещение с повторениями''' (англ. ''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>''' из (англ. ''ncombinations'' ) из <tex>n</tex> по ''<tex>k'' </tex> &mdash; это упорядоченный набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов.}}Примером сочетания может служить задача о выборе <tex>k</tex> книг из <tex>n</tex> вариантов. === Сочетания с повторениями ==={{Определение|definition='''kСочетания с повторениями''' (англ. ''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> — некоторое множество индексов, если:

== Подсчет числа Число комбинаторных объектов с помощью рекуррентных формул ==Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с {| class="wikitable" border = 1|'''Тип объекта'''||'''Число объектов'n'' предметами выражается через решение аналогичной задачи |-|Битовые векторы||<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>|-|Разбиение на неупорядоченные слагаемые||[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые]]|-|Разбиение на подмножества||[[Числа Стирлинга второго рода | Числа Стирлинга второго порядка]]|}

Пусть |proof=Число битовых векторов {{---}} это частный случай [[#5 | размещения с повторениями]] <tex>2</tex> элементов по <tex>n</tex> - число. Таким образом, которое мы разбиваем, а количество различных битовых векторов будет равно <tex>t2^n</tex> - максимальное слагаемое в разбиении, тогда количество разбиений числа на слагаемые удовлетворяет рекуррентному соотношению:.}}

{{Теорема | id=2|statement=Число различных перестановок из <tex>A(0, t) = 0n</tex>, где элементов равно <tex>t > 0P_n = n!</tex>,

|proof=Перестановка {{---}} это частный случай [[#4 | размещения]] <tex>n</tex> элементов по <tex>k</tex>A(1, 1) при <tex>k = 1n</tex>. Таким образом,количество различных перестановок будет равно <tex>n!</tex>}}

{{Теорема | id=3|statement=Число различных перестановок с повторениями из <tex>Ak</tex> элементов с <tex>n</tex> группами одинаковых элементов равно <tex>\overline{P_k} (nk_1, k_2, \ldots, tk_n) = A\frac{(nk_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n!}</tex>, t где <tex>k_i</tex> {{-- 1) + A(n - t, t)}} это количество одинаковых элементов в <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> непустых подмножеств.'''*[http:При <tex>k \geq 2</tex> воспользуемся правилом произведения. Выбрать первый элемент можно <tex>n</tex> различными способами. При каждом первом элементе, все что осталось образует размещение из оставшегося множества, то есть <tex>(n-1)</tex> элементов, по <tex>(k - 1)</neerctex>.ifmoСледовательно получаем рекуррентную формулу <tex>A_{n}^{k}=n \cdot A_{n-1}^{k-1}</tex>.ruОтсюда получаем <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</wikitex> |proof= Докажем по индукции. База: <tex>k = 1</indextex>.php?titleТогда <tex> \overline{A_n^1} =%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#n</tex>.D0 При <tex>k \geq 2</tex> воспользуемся правилом произведения. Выбрать первый элемент можно <tex>n</tex> различными способами.9FПри каждом первом элементе, все что осталось образует размещение с повторениями из того же самого множества, то есть из n элементов, по <tex>(k - 1)</tex>.D1Следовательно получаем рекуррентную формулу <tex>\overline{A_n^k} = n \cdot \overline{A_{n}^{k-1}}</tex>.80Отсюда получаем <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>.D0В каждом размещении выбраны <tex>k</tex> элементов из данного множества.B8Если игнорировать порядок этих выбранных <tex>k</tex> элементов, мы получим некоторые сочетания из данного множества по <tex>k</tex>.D0Другими словами, размещение с одним и тем же набором выбранных <tex>k</tex> элементов задают одно и то же сочетание по <tex>k</tex> элементов.BC Так как размещения с одним и тем же набором выбранных <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> единиц.D0 Будем считать нули разделителями, которые делят этот вектор на <tex>n</tex> частей.B5 Тогда предположим, что число единиц в <tex>i</tex>{{---}}м блоке {{---}} это число элементов <tex>k_i</tex> в сочетании с повторением, которое соответствует этому вектору, где <tex>k_i</tex> {{---}} это элемент из изначального множества с номером i.D0 Пример: Если у нас есть набор элементов 1 1 2 2 3, то <tex>k_2</tex> = 2.BD Получаем, что каждому сочетанию с повторениями из <tex>n</tex> по <tex>k</tex> соответствует некоторый вектор из нулей и единиц с <tex>(n+k-1)</tex> координатами, в котором <tex>(n-1)</tex> нулей.D0Также наоборот, по каждому такому вектору однозначно восстанавливается сочетание с повторением, ему соответствующее.B5Значит, число сочетаний с повторениями из <tex>n</tex> по <tex>k</tex> совпадает с числом таких векторов.D0 Таких векторов столько, сколько вариантов выбрать <tex>k</tex> координат, на которых должны стоять единицы из <tex>(n+k-1)</tex>.BDТаким образом, ответом будет являться число сочетаний из <tex>(n+k-1)</tex> по <tex>k</tex>.D0Тогда количество равно <tex> \overline{C_n^k} = C_{n+k-1}^{k}</tex>}}  == См.B8также ==*[[Генерация комбинаторных объектов в лексикографическом порядке | Генерация комбинаторных объектов в лексикографическом порядке]]*[[Получение следующего объекта | Получение следующего объекта]]*[[Получение номера по объекту | Получение номера по объекту]]*[[Получение объекта по номеру | Получение объекта по номеру]] == Примечания ==<references/> == Источники информации ==* [http://hijos.D1ru/izuchenie-matematiki/algebra-10-klass/19-razmeshheniya-perestanovki-sochetaniya-s-povtoreniyami-formula-vklyucheniya-isklyucheniya/ Математика, которая мне нравится — Размещения, перестановки, сочетания с повторениями.8F Применение чисел Стирлинга второго порядкаФормула включения – исключения]