Калькулятор таблицы чисел Стирлинга второго рода

Калькулятор таблицы чисел Стирлинга второго рода

Развивающийся AI Skill PRO

Введите расчет

Математическая формула

S(n,k)=k·S(n−1,k)+S(n−1,k−1)S(\text{n},k) = k\cdot S(\text{n}-1,\,k) + S(\text{n}-1,\,k-1)
Статистика использования

Реклама

Результаты

Число Белла B(n) = сумма строки n
4140
n = 8 · записей: 9 (k = 0 .. 8)
k S(n, k)
0 0
1 1
2 127
3 966
4 1701
5 1050
6 266
7 28
8 1

Сообщить об ошибке на этой странице

Что такое числа Стирлинга второго рода?

Число Стирлинга второго рода, обозначаемое \(S(n,k)\) (а также \(\left\{ {n \atop k} \right\}\) или \(S_2(n,k)\)), показывает, сколькими способами можно разбить множество из \(n\) помеченных (различимых) элементов ровно на \(k\) непустых неупорядоченных подмножеств — их называют блоками. Этот калькулятор вычисляет целую строку: при фиксированном \(n\) он выводит \(S(n,k)\) для \(k = 0, 1, 2, ..., n\), то есть все значения строки \(n\) треугольника Стирлинга. Это чисто математическая комбинаторная величина, которая никак не зависит от страны или региона.

Схема, на которой множество из 5 точек разбито на 2 непустые группы цветными петлями
\(S(n,k)\) считает число способов разбить \(n\) различных объектов на \(k\) непустых непомеченных групп.

Как пользоваться калькулятором

Введите неотрицательное целое число \(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,$$ однако в вычислениях с плавающей точкой она страдает от сильного взаимного сокращения слагаемых, поэтому мы используем рекуррентное соотношение с точными целыми числами.

Реклама
Схема рекуррентности: ячейка вычисляется из ячейки сверху и ячейки сверху слева
Каждый элемент строится из предыдущей строки по формуле \(S(n,k) = k\cdot S(n-1,k) + S(n-1,k-1)\).

Разбор примера (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\)).
Последнее обновление:

Самые популярные в разделе Математика и статистика

Все калькуляторы раздела Математика и статистика