Изменения
Согласно правилам русского языка, правильно будет "векторы", а не "вектора"
{{Определение
|definition = '''Комбинаторные объекты''' (англ. ''combinatorial objects'') — это конечные множества, на элементы которых могут накладываться определённые ограничения, такие как: различимость или неразличимость элементов, возможность повторения одинаковых элементов и т. п.}}
{{Определение
|definition = Если два комбинаторных объекта, различающихся только порядком элементов, считаются различными, то они называются '''упорядоченными'''(англ. ''ordered'').
}}
== Примеры комбинаторных объектов ==
=== Битовые вектора векторы ==={{Определение|definition='''[[Получение объекта по номеру#Битовые вектора векторы | Битовые векторавекторы]]''' (англ. ''bit vectors'') — последовательность нулей и единиц заданной длины. Количество таких объектов вычисляется по формуле <tex>2^{n}}</tex>, так как на каждое из <tex>n</tex> мест мы можем поставить один из двух элементов.
=== Перестановки ===
{{Определение|definition='''Перестановки<ref>[httphttps://wwwru.mathelpwikipedia.spb.ruorg/book2/tv3.htmwiki/%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'') — это упорядоченный набор чисел <tex>1, 2,\ldots, n</tex>, обычно трактуемый как биекция на множестве <tex>\{ 1, 2,\ldots, n \}</tex>, которая числу <tex>i</tex> ставит соответствие <tex>i</tex>-й элемент из набора. Количество перестановок равно }}Примером перестановки может служить задача о рассадке <tex>n</tex> человек за стол по <tex>P_n = 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> — упорядоченный набор из <tex>k</tex> различных элементов на первое место, далее поставим на второе один из некоторого <tex>n </tex>- 1элементного множества.}}Примером размещения может служить задача о рассадке <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>n \times (n - 1) {a_1, a_2, \ldots, a_n\times }</tex>... \times 1 = }}В пример можно привести следующую задачу: имеется <tex>n!</tex>книг, каждая в <tex>k</tex> экземплярах.Сколькими способами может быть сделан выбор книг из числа данных?
=== Сочетания ===
{{Определение|definition='''Сочетания<ref>[httphttps://www.mathelpru.spbwikipedia.ruorg/book2/tv3.htmwiki/%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> — это набор <tex>k</tex> элементов, выбранных из данных <tex>n</tex> элементов. Количество таких наборов вычисляется по формуле }}Примером сочетания может служить задача о выборе <tex>C^{k}_n = \frac{</tex> книг из <tex>n!}{k!(n - k)!}</tex>вариантов.
=== Размещения Сочетания с повторениями ===* {{Определение|definition='''Сочетания с повторениями'''(англ. 'Размещение'combinations with repetitions'' из ) — те же сочетания, только теперь даны <tex>n</tex> по типов элементов, из которых нужно выбрать <tex>k</tex> — это упорядоченный набор из элементов, причем элементов каждого типа неограниченное количество, и элементы одного типа должны стоять подряд друг за другом.}}В пример можно привести следующую задачу: имеется <tex>kn</tex> различных элементов некоторого пирожных. Сколько способов купить <tex>nk</tex>-элементного множества.пирожных?
=== Разбиение на неупорядоченные слагаемые ===* {{Определение|definition=[[Нахождение количества разбиений числа на слагаемые | '''Разбиение''' числа '''на неупорядоченные слагаемые''' ]] (англ. ''partition'') — это представление числа <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> различными способами. При каждом первом элементе, все что осталось образует размещение с повторениями из того же самого множества, то есть из 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>
}}
{{
Теорема | 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>. В каждом размещении выбраны <tex>k</tex> элементов из данного множества. Если игнорировать порядок этих выбранных <tex>k</tex> элементов, мы получим некоторые сочетания из данного множества по <tex>k</tex>. Другими словами, размещение с одним и тем же набором выбранных <tex>k</tex> элементов задают одно и то же сочетание по <tex>k</tex> элементов.
Так как размещения с одним и тем же набором выбранных <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> единиц.
Получаем, что каждому сочетанию с повторениями из <tex>n</tex> по <tex>k</tex> соответствует некоторый вектор из нулей и единиц с <tex>A(0n+k-1)</tex> координатами, tв котором <tex>(n-1) = 0</tex>нулей. Также наоборот, по каждому такому вектору однозначно восстанавливается сочетание с повторением, ему соответствующее. Значит, где число сочетаний с повторениями из <tex>n</tex>t по <tex> 0k</tex>,совпадает с числом таких векторов.
Таких векторов столько, сколько вариантов выбрать <tex>k</tex> координат, на которых должны стоять единицы из <tex>A(n+k-1)</tex>. Таким образом, ответом будет являться число сочетаний из <tex>(n+k-1) </tex> по <tex>k</tex>. Тогда количество равно <tex> \overline{C_n^k} = C_{n+k-1}^{k}</tex>,}}
== Источники Примечания ==
<references/>
== Источники информации ==*[http://hijos.ru.wikipedia.org/wikiizuchenie-matematiki/%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 Википедия algebra- Комбинаторика]*[http:10-klass/19-razmeshheniya-perestanovki-sochetaniya-s-povtoreniyami-formula-vklyucheniya-isklyucheniya/enМатематика, которая мне нравится — Размещения, перестановки, сочетания с повторениями.wikipedia.org/wiki/Combinatorics Wikipedia - CombinatoricsФормула включения – исключения]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Комбинаторика ]]
[[Категория: Комбинаторные объекты ]]
