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

Пусть множество Xсостоит изkразличных элементов:.Перестановкой с повторениями составабудем называть упорядоченный набор длины, в котором элементвстречается раз . Количество таких перестановок обозначается.

Пример. Из буквзапишем перестановку с повторением состава. Ее длина, причем букваaвходит 2 раза,b– 2 раза,c– один раз. Такой перестановкой будет, например,или.

Выведем формулу количества перестановок с повторениями. Занумеруем все одинаковые элементы, входящие в перестановку, различными индексами, т.е. вместо перестановки получим. Теперь все элементы перестановки различны, а количество таких перестановок равно. Первый элемент встречается в выборкераз. Уберем индексы у первого элемента (в нашем примере получим перестановку), при этом число различных перестановок уменьшится в раз, т.к. при изменении порядка одинаковых элементов наша выборка не изменится. Уберем индексы у второго элемента – число перестановок уменьшится в раз. И так далее, до элемента с номеромk– число перестановок уменьшится в раз. Получим формулу

Пример. Сколько различных “слов” можно получить, переставляя буквы слова “передача” ?

В этом слове буквы “е” и “а” встречаются два раза, остальные по одному разу. Речь идет о перестановке с повторением состава длины. Количество таких перестановок равно

.