22
правки
Изменения
→Доказательства числа комбинаторных объектов
Теорема | 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>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>n</tex> частей.
Тогда предположим, что число единиц в <tex>i</tex>{{---}}м блоке {{---}} это число элементов <tex>k_i</tex> в сочетании с повторением, которое соответствует этому вектору, где <tex>k_i</tex> {{--- }} это элемент из изначального множества с номером i.
Пример: Если у нас есть набор элементов 1 1 2 2 3, то <tex>k_2</tex> = 2.
