Числа Белла: как посчитать общее число разбиений множества через треугольник Белла?
Нужно посчитать B_n — число всех способов разбить множество из n элементов на непустые группы (на любое число групп). Знаю, что B_n = сумма чисел Стирлинга, но это O(n^2) с двумерным массивом. Есть ли удобный способ посчитать именно B_n, например через какой-то «треугольник»?
2 ответа
Да, есть треугольник Белла (треугольник Айткена) — он даёт B_n за O(n^2) времени и всего O(n) памяти, без явных чисел Стирлинга.
Правило: первая строка — [1]. Каждая новая строка начинается с последнего элемента предыдущей строки, а дальше каждый элемент = левый сосед + элемент сверху (из предыдущей строки на той же позиции). Число Белла B_n — это первый элемент n-й строки (он же последний элемент (n−1)-й).
const long long MOD = 1e9 + 7;
vector<long long> bell(int n) {
vector<long long> prev = {1}; // строка 0
vector<long long> B(n + 1);
B[0] = 1;
for (int row = 1; row <= n; row++) {
vector<long long> cur(row + 1);
cur[0] = prev.back(); // старт = последний предыдущей
for (int j = 1; j <= row; j++)
cur[j] = (cur[j-1] + prev[j-1]) % MOD;
B[row] = cur[0];
prev = cur;
}
return B;
}
Сложность O(n^2) по времени, O(n) по памяти (храним только текущую и предыдущую строки). Альтернатива — рекуррента B_{n+1} = Σ_{k=0}^{n} C(n,k)·B_k, тоже O(n^2), но требует биномиальных коэффициентов.
Интуиция за рекуррентой B_{n+1} = Σ C(n,k)·B_k: фиксируем блок, содержащий «новый» (n+1)-й элемент; в нём вместе с ним ещё какие-то n−k элементов, выбираем оставшихся k для других блоков (C(n,k) способов) и разбиваем их (B_k). Это удобно, когда биномы уже предподсчитаны. А для одного конкретного B_n при больших n по простому модулю есть и формула Добинского / методы через Стирлинга — но на школьных олимпиадах треугольник Белла почти всегда достаточен.