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

Определение. Перестановкой с повторениями из m элементов состава k₁, k₂,…,k_m называют кортеж длины суммы k₁+k₂+…+k_m, где k₁ – число повторений одного элемента множества, k₂ – число повторений другого элемента множества и т.д., k_m – количество повторений оставшегося элемента множества.

Обозначают: .

Теорема 10. Число различных перестановок с повторениями данного состава (n₁, n ,..., n ) вычисляют по форму ле

, гд е n =n₁ +n +...+ n_т.

 Рассмотрим одну перестановку и заменим в ней все одинаковые элементы разными. Тогда число различных перестановок, которые можно составить из рассматриваемой нами перестановки, по правилу произведения равно n₁, n ,..., n . Проделав это для каждой перестановки, получим n! перестановок.

Следовательно, ∙ n₁!∙n₂∙…∙n_m! = n!.

Теорема доказана.

Задача. Сколькими способами можно расставить белые фигуры: 2 коня, 2 слона, 2 ладьи, ферзя и короля на первой линии шахматной доски?

Решение. В этой задаче надо найти число кортежей длины 8, имеющих заданный состав (2, 2, 2, 1, 1). Число таких кортежей, то есть перестановок с повторениями, равно 5040.

.

Ответ: 5 040 способами.

Общую задачу о перестановках с повторениями можно сформулировать следующим образом: имеются предметы m различных типов. Сколько перестановок можно сделать, взяв n₁ элементов первого типа, n₂ типа,..., n_m элементов m-го типа?

Задача. Сколько различных буквенных комбинаций (не обязательно имеющих смысл) можно получить, переставляя буквы слова «кишмиш»?

Решение. В данном слове одна буква «к», две буквы «и», две буквы «ш», одна буква «м», всего 1+2+2+1=6 (букв).

Значит, Р(1,2,2,1)= (слов).

Ответ: 180 слов.