Перестановки с повторениями

Перестановками с повторениями из т элементов n различных типов, среди которых k₁одинаковых элементов 1-го типа, k₂одинаковых элементов 2-го типа, ... , k_nодинаковых элементов п-го типа (k₁ + k₂ + ... + k_п = m) , называются их последовательности, отличающиеся только порядком входящих в них элементов.

Пример. Перестановки из 3 элементов, среди которых 2 одинаковых элемента типа а и 1 элемент типа b: ааb, аbа, bаа.

Число перестановок из т элементов, среди которых k₁ одинаковых элементов

1-го типа, k₂ одинаковых элементов2-го типа,..., k_п одинаковых элементов n-го типа [обозначается Р (m; k₁,k₂ ,..., k_п) равно:

Р (m; k₁,k₂ ,..., k_п)= т!/ (k₁!k₂ !... k_п!).

Действительно, будем считать сначала все т элементов различными (неодинаковыми). Тогда получим m! перестановок без повто­рений. При этом мы сделали в k₁! раз больше перестановок из k₁ одинаковых элементов 1-го типа, посчитав эти элементы различными (правило умножения) . Аналогично мы сделали в k₂! раз больше перестановок из k₂одинаковых элементов 2-го типа, посчитав эти элементы различными (правило умножения) и т.д. В конце концов мы сделали в k_n! раз больше перестановок из k_n одинаковых элемен­тов n-го типа, посчитав эти элементы различными (правило умножения) . В итоге получим

Р (m; k₁,k₂ ,..., k_п)= т!/(k₁!k₂! ... k_п!).

Для примера перестановок с повторениями из 3 элементов, среди которых 2 одинаковых типа а и 1 элемент типа b, имеем Р (m=3; k₁=2,k₂=1)= 3!/ (2!1!).

Решением задачи 2 является Р(6; 3, 2, 1) = 6!/(3! 2! 1!)= 60 различных вариантов 6-значных чисел, содержащих цифру 1 трижды, 3 —дважды и 5 — один раз.