22
правки
Изменения
→Доказательства числа комбинаторных объектов.
Теорема | id=3
|statement=
Число различных перестановок с повторениями из <tex>k</tex> элементов с различными <tex>n</tex> группами одинаковых элементов равно <tex>\overline{PP_k}_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=
Теорема | id=5
|statement=
Число различных размещений с повторениями из <tex>n</tex> элементов по <tex>k</tex> равно <tex>\widetildeoverline{A}_nA_n^k } = n^k</tex>
|proof=
Докажем по индукции. База: <tex>k = 1</tex>. Тогда <tex> \widetildeoverline{A}_nA_n^1 } = n</tex>.
При <tex>k \geq 2</tex> воспользуемся правилом произведения. Выбрать первый элемент можно <tex>n</tex> различными способами. При каждом первом элементе, все что осталось образует размещение с повторениями из того же самого множества, то есть из n элементов, по <tex>(k - 1)</tex>. Следовательно получаем рекуррентную формулу <tex>\widetildeoverline{A}_nA_n^k } = n \cdot \widetildeoverline{A}_A_{n}^{k-1}}</tex>. Отсюда получаем <tex>\widetildeoverline{A}_nA_n^k}=n \cdot n \ldots = n^k </tex>
}}
Теорема | id=7
|statement=
Число различных сочетаний с повторениями из <tex>n</tex> элементов по <tex>k</tex> равно <tex>\widetildeoverline{C}^k_n } = \frac{(n + k - 1)!}{k!(n - 1)!} = C^k_{n + k - 1}</tex>
|proof=
Получаем, что каждому сочетанию с повторениями из <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> \widetildeoverline{C}_nC_n^k } = C_{n+k-1}^{k}</tex>
}}
