Числа Стирлинга второго рода: как считать разбиения множества на k непустых частей?
Нужно посчитать, сколькими способами разбить множество из n различимых элементов на ровно k непустых неразличимых групп. Это вроде числа Стирлинга второго рода S(n,k). Как их считать и чем они отличаются от обычных сочетаний и от чисел Белла?
2 ответа
Число Стирлинга второго рода S(n,k) = число способов разбить n различимых элементов на k непустых НЕразличимых блоков. Рекуррента:
S(n,k) = k · S(n−1,k) + S(n−1,k−1), S(0,0)=1, S(n,0)=0 при n>0.
Идея: n-й элемент либо кладём в один из существующих k блоков (k · S(n−1,k)), либо он образует новый блок (S(n−1,k−1)).
const int MOD = 1e9 + 7;
vector<vector<long long>> stirling2(int n) {
vector<vector<long long>> S(n+1, vector<long long>(n+1, 0));
S[0][0] = 1;
for (int i = 1; i <= n; i++)
for (int k = 1; k <= i; k++)
S[i][k] = ((long long)k * S[i-1][k] + S[i-1][k-1]) % MOD;
return S;
}
Сложность O(n^2). Отличие от сочетаний: C(n,k) выбирает k элементов из n, а S(n,k) разбивает всё множество. Число Белла B_n = Σ_{k=0}^{n} S(n,k) — это число ВСЕХ разбиений (на любое число блоков). Есть и явная формула через включение-исключение: S(n,k) = (1/k!) Σ_{j=0}^{k} (−1)^j C(k,j) (k−j)^n.
Не путай с числами Стирлинга ПЕРВОГО рода (они считают перестановки с заданным числом циклов) — у них своя рекуррента c(n,k) = c(n−1,k−1) + (n−1)·c(n−1,k). И если блоки в твоей задаче РАЗЛИЧИМЫ (например, пронумерованные коробки), то ответ — k!·S(n,k) (= число сюръекций из n-множества в k-множество), а вовсе не S(n,k).