Перестановки с повторениями. Перестановками с повторениями из т элементов n различных типов, среди которых k1одинаковых элементов 1-го типа

Перестановками с повторениями из т элементов 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 — один раз.