22
правки
Изменения
Доказательства числа комбинаторных объектов
== Число комбинаторных объектов ==
{| class="wikitable" border = 1
|'''Тип объекта'''||'''Число объектов'''
|-
|Битовые вектора||<tex>2^{n}</tex>
|-
|Перестановки||<tex>P_n = n!</tex>
|-
|Перестановки с повторениями||<tex dpi = "150">\widetilde{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 dpi = "150">A^{k}_n = \frac{n!}{(n - k)!}</tex>
|-
|Размещения с повторениями||<tex>\widetilde{A}_n^k = 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>
|-
|Разбиение на неупорядоченные слагаемые||[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые]]
|-
|Разбиение на подмножества||[[Числа Стирлинга второго рода | Числа Стирлинга второго порядка]]
|}
==Доказательства числа комбинаторных объектов.==
{{
Теорема
|statement=
Число битовых векторов равно <tex>2^{n}</tex>.
|proof=
Число битовых векторов {{---}} это частный случай размещения с повторениями <tex>2</tex> элементов по <tex>n</tex>. Таким образом ответ <tex>2^n</tex>. Смотрите доказательство размещения с повторениями.
}}
{{
Теорема
|statement=
Число перестановок равно <tex>P_n = n!</tex>
|proof=
Перестановка {{---}} это частный случай размещения <tex>n</tex> элементов по <tex>k</tex> при <tex>k = n</tex>. Таким образом смотрите доказательство размещений.
}}
{{
Теорема
|statement=
Число перестановок с повторениями равно <tex>\widetilde{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>
|proof=
Пусть нам нужно найти количество перестановок с повторениями на множестве <tex>A</tex> в котором <tex>k</tex> элементов. Будем учитывать, что в этом множестве <tex>n</tex> групп одинаковых элементов. Таким образом количество перестановок не учитывая того факта, что элементы могут быть одинаковые будет равна <tex>k!</tex> однако мы также должны учитывать то, что у нас <tex>n</tex> групп с одинаковыми элементами.
В каждой итоговой перестановке у нас будет несколько раз учитываться ситуации с одинаковыми элементами ровно столько раз, сколько можно получить перестановок из <tex>k_i</tex>. Таким образом количество перестановок с одинаковым первым элементом будет <tex>k_1!</tex>, для второго элемента {{---}} <tex>k_2!</tex>. Общее количество будет равно произведению данных факториалов. Итого одинаковых перестановок {{---}} <tex>k_1! \cdot k_2! \cdot \ldots \cdot m_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>
}}
{{
Теорема
|statement=
Число размещений равно <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>(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>
}}
{{
Теорема
|statement=
Число размещений с повторениями равно <tex>\widetilde{A}_n^k = n^k</tex>
|proof=
Доказательство по индукции. Пусть <tex>k = 1</tex>. Тогда <tex> \widetilde{A}_n^1 = n</tex>.
При <tex>k \geq 2</tex> воспользуемся правилом произведения. Выбрать первый элемент <tex>n</tex> различных значений. При любом первом элементе, все что осталось образует размещение с повторениями по <tex>(k - 1)</tex> из того же множества. Таким образом получаем рекуррентную формулу <tex>\widetilde{A}_n^k = n \cdot \widetilde{A}_{n}^{k-1}</tex>. Таким образом получаем <tex>\widetilde{A}_n^k=n \cdot n \ldots = n^k </tex>
}}
{{
Теорема
|statement=
Число сочетаний равно <tex>C^{k}_n = \frac{n!}{k!(n - k)!}</tex>
|proof=
Рассмотрим все размещения из <tex>n</tex> элементов по <tex>k</tex>. Их <tex>A_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> C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n - k)!}</tex>
}}
{{
Теорема
|statement=
Число сочетаний с повторениями равно <tex>\widetilde{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>i</tex>-м куске {{---}} это число элементов <tex>a_i</tex> в сочетании с повторением, которое соответствует этому вектору.
Получаем, что каждому сочетанию с повторениями из <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> \widetilde{C}_n^k = C_{n+k-1}^{k}</tex>
}}
{| class="wikitable" border = 1
|'''Тип объекта'''||'''Число объектов'''
|-
|Битовые вектора||<tex>2^{n}</tex>
|-
|Перестановки||<tex>P_n = n!</tex>
|-
|Перестановки с повторениями||<tex dpi = "150">\widetilde{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 dpi = "150">A^{k}_n = \frac{n!}{(n - k)!}</tex>
|-
|Размещения с повторениями||<tex>\widetilde{A}_n^k = 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>
|-
|Разбиение на неупорядоченные слагаемые||[[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые]]
|-
|Разбиение на подмножества||[[Числа Стирлинга второго рода | Числа Стирлинга второго порядка]]
|}
==Доказательства числа комбинаторных объектов.==
{{
Теорема
|statement=
Число битовых векторов равно <tex>2^{n}</tex>.
|proof=
Число битовых векторов {{---}} это частный случай размещения с повторениями <tex>2</tex> элементов по <tex>n</tex>. Таким образом ответ <tex>2^n</tex>. Смотрите доказательство размещения с повторениями.
}}
{{
Теорема
|statement=
Число перестановок равно <tex>P_n = n!</tex>
|proof=
Перестановка {{---}} это частный случай размещения <tex>n</tex> элементов по <tex>k</tex> при <tex>k = n</tex>. Таким образом смотрите доказательство размещений.
}}
{{
Теорема
|statement=
Число перестановок с повторениями равно <tex>\widetilde{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>
|proof=
Пусть нам нужно найти количество перестановок с повторениями на множестве <tex>A</tex> в котором <tex>k</tex> элементов. Будем учитывать, что в этом множестве <tex>n</tex> групп одинаковых элементов. Таким образом количество перестановок не учитывая того факта, что элементы могут быть одинаковые будет равна <tex>k!</tex> однако мы также должны учитывать то, что у нас <tex>n</tex> групп с одинаковыми элементами.
В каждой итоговой перестановке у нас будет несколько раз учитываться ситуации с одинаковыми элементами ровно столько раз, сколько можно получить перестановок из <tex>k_i</tex>. Таким образом количество перестановок с одинаковым первым элементом будет <tex>k_1!</tex>, для второго элемента {{---}} <tex>k_2!</tex>. Общее количество будет равно произведению данных факториалов. Итого одинаковых перестановок {{---}} <tex>k_1! \cdot k_2! \cdot \ldots \cdot m_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>
}}
{{
Теорема
|statement=
Число размещений равно <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>(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>
}}
{{
Теорема
|statement=
Число размещений с повторениями равно <tex>\widetilde{A}_n^k = n^k</tex>
|proof=
Доказательство по индукции. Пусть <tex>k = 1</tex>. Тогда <tex> \widetilde{A}_n^1 = n</tex>.
При <tex>k \geq 2</tex> воспользуемся правилом произведения. Выбрать первый элемент <tex>n</tex> различных значений. При любом первом элементе, все что осталось образует размещение с повторениями по <tex>(k - 1)</tex> из того же множества. Таким образом получаем рекуррентную формулу <tex>\widetilde{A}_n^k = n \cdot \widetilde{A}_{n}^{k-1}</tex>. Таким образом получаем <tex>\widetilde{A}_n^k=n \cdot n \ldots = n^k </tex>
}}
{{
Теорема
|statement=
Число сочетаний равно <tex>C^{k}_n = \frac{n!}{k!(n - k)!}</tex>
|proof=
Рассмотрим все размещения из <tex>n</tex> элементов по <tex>k</tex>. Их <tex>A_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> C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n - k)!}</tex>
}}
{{
Теорема
|statement=
Число сочетаний с повторениями равно <tex>\widetilde{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>i</tex>-м куске {{---}} это число элементов <tex>a_i</tex> в сочетании с повторением, которое соответствует этому вектору.
Получаем, что каждому сочетанию с повторениями из <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> \widetilde{C}_n^k = C_{n+k-1}^{k}</tex>
}}
