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

Перестановки с повторениями Перестановки с повторениями возникают в ситуации, когда нам нужно составить перестановки из N элементов, некоторые из которых одинаковые.

Чтобы лучше понять данный тип комбинаций, начнем со случая, когда эти N элементов делятся на 2 группы, внутри которых они неотличимы друг от друга.

 
Количество перестановок с повторениями
(для 2-х групп)
Пусть имеется N карточек, на k из которых написана буква A, а на остальных l карточках - буква B (разумеется, k + l = N). Сколько разных слов можно составить, переставляя их между собой?

Если бы все карточки были разные, то каждое их расположение в ряд было бы перестановкой из N элементов, и всего таких расположений мы насчитали бы N! Поскольку карточки с буквами А (равно как и с буквой B) выглядят для нас одинаковыми, то их перестановки между собой (A с A, B с B) не изменяют слова. Следовательно, при подсчете перестановок каждое слово (перестановка с повторениями) было посчитано столько раз, сколькими способами можно переставить k букв A между собой и l букв B между собой, т.е. k!·l! раз. Поделив N! на k!·l!, получаем интересующее нас количество перестановок с повторениями:

При доказательстве формулы мы воспользовались еще одним замечательным комбинаторным правилом: если при подсчете комбинаций каждая из них была посчитана m раз, то нужно поделить найденное количество на m. Оно называется правилом деления.

 
Количество перестановок с повторениями
(общий случай)
Рассмотрим теперь общий случай перестановок с повторениями. Пусть имеется N элементов, которые делятся на k групп по n1, n2, ... nk элементов в каждой, причем внутри одной группы элементы друг от друга неотличимы (разумеется, n1+n2+...+nk=N). Общее число перестановок, которые можно отличить друг от друга, будет равно:

Действительно, если бы все элементы были разными, то общее число перестановок было бы N!. Какие же из них неотличимы друг от друга? Те, что отличаются перестановками элементов внутри каждой из групп. В первой группе элементы можно переставить n1! способами, во второй - n2! и так далее. Значит, каждая перестановка повторятся в нашем подсчете n1!·n2!·...·nk! раз. Чтобы посчитать ее только один раз, нужно, по правилу деления, поделить N! на n1!·n2!·...·nk!.