Перестановки с повторениями: формула и примеры

Перестановки с повторениями появляются всюду, где надо посчитать, сколькими способами можно расставить в ряд объекты, среди которых есть одинаковые: буквы в слове, цветные шары, флажки, шаги маршрута. Обычная формула числа перестановок $n!$ здесь даёт неверный ответ, потому что она считает разными те расстановки, которые на самом деле неотличимы. Ниже разберём, как устроена правильная формула, почему в знаменателе стоят факториалы повторов, и решим несколько типовых задач. Чтобы сразу почувствовать, как меняется ответ от числа повторов, покрутите калькулятор ниже: задайте, сколько раз встречается каждая буква, и он мгновенно покажет общее число объектов, знаменатель и итог.

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

Перестановка с повторениями - это упорядоченное расположение в ряд объектов из мультимножества, то есть набора, в котором некоторые элементы повторяются. Если бы все объекты были различны, число способов их упорядочить равнялось бы $n!$, где $n$ - общее количество объектов. Но когда часть элементов одинакова, многие расстановки выглядят одинаково, и считать их по отдельности нельзя.

Возьмём слово из двух одинаковых букв, например ОО. Если бы буквы различались (О и о), было бы $2! = 2$ перестановки: Оо и оО. Но буквы неотличимы, поэтому обе расстановки дают одно и то же слово ОО. Реально различимая перестановка всего одна. Именно это деление на «лишние» варианты и зашито в формулу перестановок с повторениями.

Формула перестановок с повторениями

Пусть всего $n$ объектов, среди которых $r$ различных типов, и тип с номером $i$ встречается $n_i$ раз, причём $n_1 + n_2 + \dots + n_r = n$. Тогда число различимых перестановок равно

$P(n; n_1, n_2, \dots, n_r) = \frac{n!}{n_1!\, n_2! \cdots n_r!}.$

В числителе стоит $n!$ - число расстановок, как если бы все объекты были разными. В знаменателе - произведение факториалов кратностей: каждая группа из $n_i$ одинаковых элементов может быть переставлена внутри себя $n_i!$ способами, и все эти перестановки дают один и тот же видимый результат. Поэтому мы делим на каждый такой множитель, убирая повторный счёт.

Рассчитать для своей задачи

Видно главную идею: каждый множитель в знаменателе ровно убирает столько повторов, сколько даёт перестановка одинаковых элементов между собой. Если все элементы различны, все $n_i = 1$, факториалы единиц равны единице, и формула превращается в обычную $P = n!$.

Разбор слова МАТЕМАТИКА

Это классический школьный пример. В слове МАТЕМАТИКА десять букв: $n = 10$. Посчитаем, сколько раз встречается каждая буква:

• М встречается 2 раза;
• А встречается 3 раза;
• Т встречается 2 раза;
• Е, И, К - по 1 разу.

Подставляем в формулу. В знаменателе берём только буквы, повторяющиеся больше одного раза (факториал единицы равен единице и ничего не меняет):

$P = \frac{10!}{2!\, 3!\, 2!} = \frac{3\,628\,800}{2 \cdot 6 \cdot 2} = \frac{3\,628\,800}{24} = 151\,200.$

Итого из букв слова МАТЕМАТИКА можно составить 151 200 различных перестановок. Тот же результат показывает калькулятор выше при настройках по умолчанию: общее число объектов 10, знаменатель 24, итог 151 200.

Рассчитать для своей задачи

Обратите внимание: если ошибочно посчитать просто $10! = 3\,628\,800$, ответ окажется завышен в 24 раза. Именно во столько раз больше, во сколько способов одинаковые М, А и Т можно переставить между собой, не меняя слова.

Перестановки одинаковых предметов: шары и флажки

Формула не привязана к буквам - она работает для любых одинаковых предметов. Пусть надо выложить в ряд 3 красных, 2 синих и 4 зелёных одинаковых шара. Всего шаров $n = 3 + 2 + 4 = 9$, повторы - 3, 2 и 4:

$P = \frac{9!}{3!\, 2!\, 4!} = \frac{362\,880}{6 \cdot 2 \cdot 24} = \frac{362\,880}{288} = 1260.$

Рассчитать для своей задачи

Логика та же, что и со словом: внутри каждого цвета шары неразличимы, поэтому их перестановки между собой не создают новых раскладов, и мы делим на $3!$, $2!$ и $4!$. Точно так же считаются флажки, кубики, символы в коде и любые объекты, разбитые на группы одинаковых.

Связь с биномиальными коэффициентами и маршрутами

Когда типов всего два, формула перестановок с повторениями превращается в биномиальный коэффициент. Расстановка $k$ единиц и $n - k$ нулей в строке длины $n$ - это

$\frac{n!}{k!\,(n-k)!} = \binom{n}{k},$

то есть число сочетаний. Поэтому задачи про кратчайшие маршруты по сетке решаются именно этой формулой: путь из угла в угол сетки $a$ на $b$ - это последовательность из $a$ шагов вправо и $b$ шагов вверх, а число таких последовательностей равно $\frac{(a+b)!}{a!\,b!}$. Для сетки 4 на 3 получаем $\frac{7!}{4!\,3!} = 35$ путей. Перестановки с повторениями и сочетания - это, по сути, один и тот же объект, записанный по-разному.

Частые ошибки

• Считают $n!$ и забывают про повторы. Это самая частая ошибка: ответ завышается ровно в $n_1!\,n_2!\cdots$ раз. Всегда проверяйте, нет ли одинаковых элементов.
• Делят не на факториалы, а на сами кратности. В знаменателе стоит $n_i!$, а не $n_i$. Для слова МАТЕМАТИКА это $2!\,3!\,2! = 24$, а не $2 \cdot 3 \cdot 2 = 12$.
• Учитывают буквы, встречающиеся один раз. Их факториал равен $1!=1$ и на ответ не влияет, но иногда их по ошибке пропускают при подсчёте $n$, занижая общее число объектов.
• Путают сумму кратностей с числом типов. В знаменателе перемножаются факториалы по всем типам, а в числителе стоит $n$ - сумма всех кратностей, а не количество разных букв.
• Применяют формулу там, где порядок не важен. Если расстановка в ряд не нужна (например, просто выбор подмножества), это уже сочетания или разбиения, а не перестановки.

FAQ

Чем перестановки с повторениями отличаются от обычных перестановок? Обычные перестановки считают все $n$ объектов различными и дают $n!$ вариантов. Перестановки с повторениями учитывают, что часть объектов одинакова, и делят $n!$ на факториалы кратностей, убирая неотличимые расстановки.

Что если все элементы разные? Тогда каждая кратность $n_i = 1$, все факториалы в знаменателе равны единице, и формула сводится к обычной $P = n!$. Перестановки без повторений - это частный случай формулы с повторениями.

Как связаны перестановки с повторениями и сочетания? При двух типах объектов формула $\frac{n!}{k!\,(n-k)!}$ совпадает с биномиальным коэффициентом $\binom{n}{k}$. Поэтому задачи на маршруты по сетке и расстановку двух видов предметов решаются как сочетаниями, так и через перестановки с повторениями - это одно и то же число.

Коротко

Перестановки с повторениями считают, сколькими способами можно расставить в ряд объекты, среди которых есть одинаковые. Формула $P = \dfrac{n!}{n_1!\,n_2!\cdots n_r!}$ берёт все $n!$ расстановок и делит на факториалы кратностей, потому что перестановки одинаковых элементов между собой не дают новых вариантов. Для слова МАТЕМАТИКА это $\frac{10!}{2!\,3!\,2!} = 151\,200$. При двух типах формула превращается в биномиальный коэффициент, поэтому ею же решаются задачи про шары, флажки и кратчайшие маршруты по сетке.