Как посчитать число сюръекций из n-множества в k-множество (раскраски, где все цвета использованы)?
Нужно посчитать, сколькими способами раскрасить n различных предметов в k цветов так, чтобы КАЖДЫЙ из k цветов был использован хотя бы раз. Без ограничения было бы k^n, но как учесть «все цвета встречаются»? Похоже на включение-исключение, но не соберу формулу.
2 ответа
Это число сюръекций (наложений) из множества размера n на множество размера k. Cчитается включением-исключением по «запрещённым» (неиспользованным) цветам:
Surj(n, k) = Σ_{j=0}^{k} (−1)^j · C(k, j) · (k − j)^n.
Идея ВИ: из всех k^n раскрасок вычитаем те, где хоть один цвет пропущен. A_i — раскраски без цвета i, |A_i| = (k−1)^n, пересечение по j цветам — (k−j)^n, выбор j пропущенных — C(k,j), знак чередуется.
const long long MOD = 1e9 + 7;
long long power(long long a,long long b){long long r=1;a%=MOD;while(b){if(b&1)r=r*a%MOD;a=a*a%MOD;b>>=1;}return r;}
// C(k,j) через предподсчитанные факториалы
long long surjections(int n, int k) {
long long res = 0;
for (int j = 0; j <= k; j++) {
long long term = C(k, j) * power(k - j, n) % MOD;
if (j & 1) res = (res - term + MOD) % MOD;
else res = (res + term) % MOD;
}
return res;
}
Сложность O(k log n) (степень за log n на каждое слагаемое). Связь: Surj(n,k) = k! · S(n,k), где S(n,k) — число Стирлинга второго рода (раздели на цвета-блоки, потом раскрась блоки в цвета k! способами).
Грабли: (1) обязательно приводить отрицательное по модулю через + MOD; (2) при j=k слагаемое (k−j)^n = 0^n, и для n≥1 оно нулевое — а вот 0^0 = 1, так что при n=0 формула тоже отрабатывает корректно, если степень определена как power(0,0)=1. (3) Если k > n, сюръекций нет (Surj=0) — формула это сама даёт, но можно отсечь сразу для скорости.