Обсуждение участника:Galibov Mikhail — различия между версиями
(→Число комбинаторных объектов) |
(→Доказательства числа комбинаторных объектов) |
||
Строка 60: | Строка 60: | ||
|proof= | |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> | При <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> | ||
Строка 84: | Строка 84: | ||
|proof= | |proof= | ||
− | Всего размещений из <tex>n</tex> элементов по <tex>k</tex> равно <tex>A_n^k = \frac{n!}{(n - k)!}</tex>. В каждом размещении выбраны | + | Всего размещений из <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> | Так как размещения с одним и тем же набором выбранных <tex>k</tex> элементов различаются только порядком элементов и число различных перестановок из <tex>k</tex> элементов равно <tex>k!</tex>, то итоговая формула будет равна <tex>C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n - k)!}</tex> | ||
Строка 100: | Строка 100: | ||
Будем считать нули разделителями, которые делят этот вектор на <tex>n</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>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>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> |
}} | }} |
Версия 16:54, 5 января 2021
Количество комбинаторных объектов
Тип объекта | Количество различных объектов |
Битовые вектора | |
Перестановки | |
Перестановки с повторениями | |
Размещения | |
Размещения с повторениями | |
Сочетания | |
Сочетания с повторениями | |
Разбиение на неупорядоченные слагаемые | Нахождение количества разбиений числа на слагаемые |
Разбиение на подмножества | Числа Стирлинга второго порядка |
Доказательства числа комбинаторных объектов
Теорема: |
Число различных битовых векторов равно . |
Доказательство: |
Число битовых векторов — это частный случай размещения с повторениями элементов по . Таким образом, количество различных битовых векторов будет равно . |
Теорема: |
Число различных перестановок из элементов равно |
Доказательство: |
Перестановка — это частный случай размещения элементов по при . Таким образом, количество различных перестановок будет равно |
Теорема: |
Число различных перестановок с повторениями из элементов с различными группами одинаковых элементов равно |
Доказательство: |
Пусть нужно найти количество перестановок с повторениями на множестве из элементов. Будем учитывать, что в этом множестве групп одинаковых элементов. Количество перестановок из элементов, не учитывая того факта, что элементы могут быть одинаковые, будет равна , однако мы также должны учитывать то, что у нас групп с одинаковыми элементами.В каждой итоговой перестановке у нас будет несколько раз учитываться ситуации с одинаковыми элементами ровно столько раз, сколько можно получить перестановок из Получаем, что итоговое количество равно . Таким образом количество перестановок с одинаковым первым элементом будет равно , для второго элемента — . Общее количество идентичных перестановок будет равно произведению данных факториалов. Итого одинаковых перестановок . Ответом будем являться частное количества всех перестановок и количества одинаковых. |
Теорема: |
Число различных размещений из элементов по равно |
Доказательство: |
Доказательство по индукции. База При , тогда количество размещений из по равно . воспользуемся правилом произведения. Выбрать первый элемент можно различными способами. При каждом первом элементе, все что осталось образует размещение из оставшегося множества, то есть элементов, по . Следовательно получаем рекуррентную формулу . Отсюда получаем |
Теорема: |
Число различных размещений с повторениями из элементов по равно |
Доказательство: |
Докажем по индукции. База: При . Тогда . воспользуемся правилом произведения. Выбрать первый элемент можно различными способами. При каждом первом элементе, все что осталось образует размещение с повторениями из того же самого множества, то есть из n элементов, по . Следовательно получаем рекуррентную формулу . Отсюда получаем |
Теорема: |
Число различных сочетаний из элементов по равно |
Доказательство: |
Всего размещений из Так как размещения с одним и тем же набором выбранных элементов по равно . В каждом размещении выбраны элементов из данного множества. Если игнорировать порядок этих выбранных элементов, мы получим некоторые сочетания из данного множества по . Другими словами, размещение с одним и тем же набором выбранных элементов задают одно и то же сочетание по элементов. элементов различаются только порядком элементов и число различных перестановок из элементов равно , то итоговая формула будет равна |
Теорема: |
Число различных сочетаний с повторениями из элементов по равно |
Доказательство: |
Рассмотрим двоичный вектор из координат, в котором нулей и единиц.Будем считать нули разделителями, которые делят этот вектор на частей.Тогда предположим, что число единиц в -м куске — это число элементов в сочетании с повторением, которое соответствует этому вектору.Получаем, что каждому сочетанию с повторениями из Таких векторов столько, сколько вариантов выбрать по соответствует некоторый вектор из нулей и единиц с координатами, в котором нулей. Также наоборот, по каждому такому вектору однозначно восстанавливается сочетание с повторением, ему соответствующее. Значит число сочетаний с повторениями из по совпадает с числом таких векторов. координат, на которых должны стоять единицы из . Таким образом, ответом будет являться число сочетаний из по . Тогда количество равно |