Перестановки с повторениями: формула для мультимножества (как «МИССИСИПИ»)?
Сколько различных слов можно составить, переставляя буквы слова, в котором некоторые буквы повторяются (классика — MISSISSIPPI)? Понимаю, что n! делится на что-то, но всё время путаюсь, на что именно. Какая общая формула и как её аккуратно посчитать по модулю?
2 ответа
Если всего n элементов, и они делятся на группы одинаковых размеров n_1, n_2, ..., n_k (n_1 + ... + n_k = n), то число различных перестановок (мультиномиальный коэффициент):
n! / (n_1! · n_2! · ... · n_k!).
Интуиция: всего n! перестановок, если бы все были различны; но внутри каждой группы одинаковых элементов их n_i! внутренних перестановок дают одно и то же слово, поэтому делим. Для MISSISSIPPI: n=11, M=1, I=4, S=4, P=2 → 11!/(1!·4!·4!·2!) = 34650.
По модулю — через факториалы и обратные факториалы:
// fact, inv_fact предподсчитаны mod p
long long multinomial(int n, vector<int>& cnt) {
long long res = fact[n];
for (int c : cnt) res = res * inv_fact[c] % MOD;
return res;
}
Сложность O(k) на запрос после O(n) предподсчёта. Это прямое обобщение C(n,k) = n!/(k!(n−k)!), которое и есть мультиномиальный коэффициент с двумя группами.
Полезно видеть связь со «звёздами и палочками» и биномом: мультиномиальный коэффициент C(n; n_1,...,n_k) — это коэффициент при x_1^{n_1}...x_k^{n_k} в разложении (x_1+...+x_k)^n. Поэтому, например, число способов выбрать упорядоченное разбиение n людей на команды фиксированных размеров — ровно эта формула.