Изменения

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

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

=== Битовые вектора векторы ==={{Определение|definition='''[[Получение объекта по номеру#Битовые вектора векторы | Битовые векторавекторы]]''' (англ. ''bit vectors'') &mdash; последовательность нулей и единиц заданной длины. Количество таких объектов вычисляется по формуле <tex>2^{n}}</tex>, так как на каждое из <tex>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>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='''Перестановки с повторениями''' (англ. ''permutations with repetitions'') — это те же перестановки, однако некоторые элементы могут встречаться несколько раз. Число различных перестановок с повторениями из элементов }}В пример можно привести следующую задачу: имеется набор книг <tex>\{a_1, a_2, ...\ldots, a_n\}</tex>, каждая из которых имеется в которых эти элементы повторяются соответственно <tex>k_1, k_2, ..., k_n</tex> раз, равно <tex dpi = "150">\frac{(k_1 + k_2 + ... + k_n)!}{k_1!k_2!...k_n!}</tex>. Выведем формулу. Всего перестановок <tex>(k_1 + k_2 + ... + k_n)!</tex>, однако среди них есть и повторяющиеся. Такие попадаютсяldots, когда мы переставляем местами одинаковые элементы. Тогда всего повторяющихся перестановок будет в <tex>k_1!k_2!...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 dpi = "150">A^{k}_n = \frac{n!}{(n - k)!}Примером размещения может служить задача о рассадке </tex>. Выведем формулу подобно тому, как выводили для '''перестановок''': на первое место можно поставить один из <tex>nk</tex> элементов, на следующее один из человек за стол по <tex>n - 1</tex>местам,... и на последнее один из где <tex>n - k + 1</tex>. Всего получится <tex dpi = "150">n \times (n - 1) \times ... \times (n - k + 1) = \frac{n!}{(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 dpi = "150">C^{k}_n = \frac{n!}{k!(n - k)!}</tex>. Выведем данную формулу из формулы размещений, а именно заметим, что в размещениях порядок элементов имеет значение, а в сочетаниях нет. Это значит, что наборы <tex>\{1, 2\}</tex> и <tex>\{2, 1\}</tex> эквивалентны. То есть в размещениях любой вариант Примером сочетания повторяется столько же раз, сколько можно сделать перестановок для может служить задача о выборе <tex>k</tex> мест. Тогда книг из <tex dpi = "150">C^{k}_n = \frac{A^{k}_n}{k!} = \frac{n!}{k!(n - k)!}</tex>вариантов.

{{Определение|definition='''Сочетания с повторениями''' (англ. ''combinations with repetitions'') — это те же сочетания, только теперь даны <tex>n</tex> типов элементов, из которых нужно выбрать <tex>k</tex> элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом. Способов таких выборов всего <tex dpi = "150">\widetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex>. Чтобы вывести формулу, давайте различные элементы в перестановке разделим перегородками, а каждый элемент назовем <tex>1</tex>, тогда, чтобы получить новую перестановку просто будем менять местами перегородки и <tex>1</tex>, причем таких перегородок будет В пример можно привести следующую задачу: имеется <tex>n - 1</tex>, даже если мы не брали некоторые типы элементовпирожных. Таких перестановок Сколько способов купить <tex>(n - 1 + k)!</tex>, а за вычетом перестановок одинаковых элементов (перегородок и <tex>1</tex>), коих в <tex>k!(n - 1)!</tex> раз больше необходимых, получаем необходимую формулу.пирожных?

{{Определение|definition=[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''']] (англ. ''partition'') &mdash; это представление числа <tex>n</tex> в виде суммы слагаемых. Всего таких разбиений::<p><tex>P_{n,k} = \left \{ \begin{array}{ll} P_{n,k - 1} + P_{n - k, k}, & 0 < k \leqslant n \\ P_{n, n}, & k > n \\1, & n = 0, k = 0 \\0, & n \neq 0 , k = 0, \end{array} \right.</tex></p>где <tex>k</tex> — число, не превышаемое слагаемыми, причем начальное значение <tex>k = n</tex>. Вывод формулы можно найти [[main|Нахождение количества разбиений числа на слагаемые | здесь]].}}

{{Определение|definition=[[Числа Стирлинга второго рода | '''Разбиение''' множества <math>X</math> '''на подмножества''']] (англ. ''partition of a set'') — это семейство непустых множеств <math>\{U_{\alpha}\},{\alpha \in A}</math>, где <math>A</math> — некоторое множество индексов, если:

Если задано множество из }}{{main|Числа Стирлинга второго рода}} == Число комбинаторных объектов =={| class="wikitable" border = 1|'''Тип объекта'''||'''Число объектов'''|-|Битовые векторы||<tex>2^{n}</tex> элементов, которое необходимо разбить на |-|Перестановки||<tex>kP_n = n!</tex> непустых частей, то последний элемент исходного множества можно либо поместить в отдельную часть |-|Перестановки с повторениями||<tex dpi = "150">\frac{(k_1 + k_2 + \ldots + k_n)!}{k_1!k_2!\ldots k_n!}</tex>|-|Размещения||<tex dpi = "180150">A^{k}_n = \lbracefrac{n!}{(n-1\atop k-1)!}\rbrace</tex> способами), либо поместить его в некоторое подмножество (|-|Размещения с повторениями||<tex>n^k</tex>|-|Сочетания||<tex dpi = "180150">C^{k}_n = \lbracefrac{n!}{k!(n-1\atop k)!}\rbrace</tex> способами, поскольку каждый из |-|Сочетания с повторениями||<tex dpi = "180150">\lbracewidetilde{C}^k_n = \frac{(n + k - 1)!}{k!(n-1\atop )!} = 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>.}}\rbrace {{Теорема | id=2|statement=Число различных перестановок из <tex>n</tex> способов распределения первых элементов равно <tex>P_n = n!</tex> |proof=Перестановка {{-1--}} это частный случай [[#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>\beginfrac{k!}{k_1! \cdot k_2! \cdot \ldots \cdot k_n!} = \frac{Bmatrix(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 \endgeq 2</tex> воспользуемся правилом произведения. Выбрать первый элемент можно <tex>n</tex> различными способами. При каждом первом элементе, все что осталось образует размещение из оставшегося множества, то есть <tex>(n-1)</tex> элементов, по <tex>(k - 1)</tex>. Следовательно получаем рекуррентную формулу <tex>A_{Bmatrixn}^{k} = n \begincdot A_{casesn-1}^{k\begin-1}</tex>. Отсюда получаем <tex>A_{n}^{Bmatrixk}= 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> \endoverline{BmatrixA_n^1} + = n</tex>. При <tex>k \geq 2</tex> воспользуемся правилом произведения. Выбрать первый элемент можно <tex>n</tex> различными способами. При каждом первом элементе, все что осталось образует размещение с повторениями из того же самого множества, то есть из n элементов, по <tex>(k - 1)</tex>. Следовательно получаем рекуррентную формулу <tex>\beginoverline{BmatrixA_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 -1k)!}</tex> |proof= Всего размещений из <tex>n</tex> элементов по <tex>k</tex> равно <tex>A_n^k = \endfrac{Bmatrixn!}{(n - k)!}</tex>. В каждом размещении выбраны <tex>k</tex> элементов из данного множества. Если игнорировать порядок этих выбранных <tex>k</tex> элементов, 0мы получим некоторые сочетания из данного множества по <tex>k<n \\/tex>. Другими словами, размещение с одним и тем же набором выбранных <tex>k</tex> элементов задают одно и то же сочетание по <tex>k</tex> элементов. 0Так как размещения с одним и тем же набором выбранных <tex>k</tex> элементов различаются только порядком элементов и число различных перестановок из <tex>k</tex> элементов равно <tex>k!</tex>, то итоговая формула будет равна <tex>C_n^k = 0 \frac{A_n^k}{k!} = \frac{n!}{k!(n - k)!}</tex>0, }} {{Теорема | id=7|statement=Число различных сочетаний с повторениями из <tex>n </tex> элементов по <tex>k</tex> равно <tex>\overline{C^k_n} = 0 \\frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex> |proof= 0Рассмотрим двоичный вектор из <tex>(n+k-1)</tex> координат, в котором <tex>(n-1)</tex> нулей и <tex>k </tex> единиц.  Будем считать нули разделителями, которые делят этот вектор на <tex> n \\</tex> частей. Тогда предположим, что число единиц в <tex>i</tex>{{---}}м блоке {{---}} это число элементов <tex>k_i</tex> в сочетании с повторением, которое соответствует этому вектору, где <tex>k_i</tex> {{---}} это элемент из изначального множества с номером i. Пример: Если у нас есть набор элементов 11 2 2 3, то <tex>k_2</tex> = 2. Получаем, что каждому сочетанию с повторениями из <tex>n</tex> по <tex>k</tex> соответствует некоторый вектор из нулей и единиц с <tex>(n+k = -1)</tex> координатами, в котором <tex>(n-1)</tex> нулей. Также наоборот, по каждому такому вектору однозначно восстанавливается сочетание с повторением, ему соответствующее. Значит, число сочетаний с повторениями из <tex>n</tex> по <tex>k</tex> совпадает с числом таких векторов.  Таких векторов столько, сколько вариантов выбрать <tex>k</tex> координат, на которых должны стоять единицы из <tex>(n+k-1)</tex>. Таким образом, ответом будет являться число сочетаний из <tex>(n+k-1)</tex> по <tex>k</tex>. Тогда количество равно <tex> \endoverline{C_n^k} = C_{n+k-1}^{casesk}</tex>}}

== Источники информации См. также ==* [http://hijos.ru/izuchenie-matematiki/algebra-10-klass/19-razmeshheniya-perestanovki-sochetaniya-s-povtoreniyami-formula-vklyucheniya-isklyucheniya/ Размещения, перестановки, сочетания с повторениями[Генерация комбинаторных объектов в лексикографическом порядке | Генерация комбинаторных объектов в лексикографическом порядке]]*[[Получение следующего объекта | Получение следующего объекта]]*[[Получение номера по объекту | Получение номера по объекту]]*[[Получение объекта по номеру | Получение объекта по номеру]]