Что такое числа Стирлинга второго рода?
Число Стирлинга второго рода, обозначаемое \(S(n,k)\) (а также \(\left\{ {n \atop k} \right\}\) или \(S_2(n,k)\)), показывает, сколькими способами можно разбить множество из \(n\) помеченных (различимых) элементов ровно на \(k\) непустых неупорядоченных подмножеств — их называют блоками. Этот калькулятор вычисляет целую строку: при фиксированном \(n\) он выводит \(S(n,k)\) для \(k = 0, 1, 2, ..., n\), то есть все значения строки \(n\) треугольника Стирлинга. Это чисто математическая комбинаторная величина, которая никак не зависит от страны или региона.
Как пользоваться калькулятором
Введите неотрицательное целое число \(n\) (количество элементов в множестве) и нажмите кнопку расчёта. Инструмент вернёт таблицу из двух столбцов — \(k\) и \(S(n,k)\), — а также сумму строки, которая равна числу Белла \(B(n)\) и служит удобной проверкой правильности. Все значения считаются в целых числах произвольной точности, поэтому остаются точными, даже когда вырастают далеко за пределы 64-битного числа (а это происходит уже при \(n \approx 20\text{–}25\)).
Разбираем формулу
Самый надёжный способ — рекуррентное соотношение $$S(n,k) = k\cdot S(n-1,k) + S(n-1,k-1),$$ которое строится от базового случая \(S(0,0) = 1\). Граничные значения таковы: \(S(n,0) = 0\) при \(n \ge 1\), \(S(n,n) = 1\), \(S(n,1) = 1\) при \(n \ge 1\) и \(S(n,k) = 0\) при \(k > n\). Существует и явная формула: $$S(n,k) = \frac{1}{k!} \sum (-1)^{k-j} \binom{k}{j} j^n,$$ однако в вычислениях с плавающей точкой она страдает от сильного взаимного сокращения слагаемых, поэтому мы используем рекуррентное соотношение с точными целыми числами.
Разбор примера (n = 5)
Строка 5 выглядит так: \(k=0 \rarr 0\), \(k=1 \rarr 1\), \(k=2 \rarr 15\), \(k=3 \rarr 25\), \(k=4 \rarr 10\), \(k=5 \rarr 1\). Проверим её по строке \(4 = [0,1,7,6,1]\): $$S(5,2) = 2\cdot 7 + 1 = 15,$$ $$S(5,3) = 3\cdot 6 + 7 = 25,$$ $$S(5,4) = 4\cdot 1 + 6 = 10.$$ Сумма строки равна \(0+1+15+25+10+1 = 52\), что совпадает с числом Белла \(B(5) = 52\).
Частые вопросы
Почему \(S(n,0) = 0\) при \(n \ge 1\)? Непустое множество нельзя разбить на ноль блоков; только у пустого множества есть пустое разбиение, что и даёт \(S(0,0) = 1\).
Что показывает сумма строки? Сумма \(S(n,k)\) по всем \(k\) равна числу Белла \(B(n)\) — общему числу разбиений множества из \(n\) элементов.
Насколько большим может быть n? Калькулятор допускает значения до \(n = 200\); числа становятся колоссальными, но остаются абсолютно точными благодаря арифметике больших целых чисел.
