22
правки
Изменения
→Доказательства числа комбинаторных объектов.
|proof=
Пусть нам нужно найти количество перестановок с повторениями на множестве <tex>A</tex> в котором из <tex>k</tex> элементов. Будем учитывать, что в этом множестве <tex>n</tex> групп одинаковых элементов. Количество перестановок из <tex>k</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>
}}
|proof=
При <tex>k \geq 2</tex> воспользуемся правилом произведения. Выбрать первый элемент можно <tex>n</tex> различными способами. При каждом первом элементе, все что осталось образует размещение с повторениями из того же самого множества, то есть из n элементов, по <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>
|proof=
Так как размещения с одним и тем же набором выбранных <tex>k</tex> элементов различаются только порядком элементов и число различных перестановок из <tex>k</tex> элементов равно <tex>k!</tex>, то итоговая формула будет равна <tex> C_n^k = \frac{A_n^k}{k!} = \frac{n!}{k!(n - k)!}</tex>
}}
|proof=
Рассмотрим двоичный вектор из <tex>(n+k-1)</tex> координат, состоящий из нулей и единиц, в котором <tex>(n-1)</tex> нулей и <tex>k</tex> единиц.
Будем считать нули разделителями, которые делят этот вектор на <tex>n</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>
}}
