Что такое числа Стирлинга второго рода?
Число Стирлинга второго рода, обозначаемое \(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\); числа становятся колоссальными, но остаются абсолютно точными благодаря арифметике больших целых чисел.
Числа Стирлинга второго рода (строки 0–8) и числа Белла
Число Стирлинга второго рода \(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\ge 1\). Сумма по строке есть число Белла \(B(n)=\sum_{k=0}^{n} S(n,k)\), то есть общее количество разбиений множества из \(n\) элементов.
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | Сумма по строке B(n) |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | ||||||||
| 1 | 0 | 1 | 1 | |||||||
| 2 | 0 | 1 | 1 | 2 | ||||||
| 3 | 0 | 1 | 3 | 1 | 5 | |||||
| 4 | 0 | 1 | 7 | 6 | 1 | 15 | ||||
| 5 | 0 | 1 | 15 | 25 | 10 | 1 | 52 | |||
| 6 | 0 | 1 | 31 | 90 | 65 | 15 | 1 | 203 | ||
| 7 | 0 | 1 | 63 | 301 | 350 | 140 | 21 | 1 | 877 | |
| 8 | 0 | 1 | 127 | 966 | 1701 | 1050 | 266 | 28 | 1 | 4140 |
Пустые ячейки соответствуют позициям, где \(k>n\); по определению они равны нулю.
Как читать таблицу
- Проверка рекуррентного соотношения: \(S(8,3) = 3\cdot S(7,3) + S(7,2) = 3\cdot 301 + 63 = 903 + 63 = 966\).
- Ещё одна проверка: \(S(8,4) = 4\cdot S(7,4) + S(7,3) = 4\cdot 350 + 301 = 1400 + 301 = 1701\).
- Проверка суммы по строке для \(n=5\): \(0+1+15+25+10+1 = 52 = B(5)\).
- Граничные значения: \(S(n,1)=1\) и \(S(n,n)=1\); также \(S(n,2)=2^{n-1}-1\) (например, \(S(8,2)=127\)).