Что такое число Стирлинга второго рода?
Число Стирлинга второго рода, обозначаемое \(S(n,k)\), показывает, сколькими способами можно разбить множество из n различных (помеченных) элементов ровно на k непустых неупорядоченных подмножеств. Это одна из ключевых величин комбинаторики: она возникает в задачах о разбиениях множеств, о сюръекциях и тесно связана с числами Белла. Инструмент относится к чистой математике и работает одинаково в любой стране — никаких национальных особенностей здесь нет.
Как пользоваться калькулятором
Введите размер множества \(n\) и число подмножеств \(k\). Оба значения должны быть неотрицательными целыми числами. Нажмите «Рассчитать» и получите точное значение \(S(n,k)\) — количество разбиений. Если k больше n, результат равен 0: нельзя заполнить больше непустых подмножеств, чем у вас есть элементов.
Разбор формулы
Явная формула выглядит так: $$S(n,k) = \frac{1}{k!}\sum_{j=0}^{k} (-1)^{k-j}\binom{k}{j}\,j^{n}$$ где \(C(k,j)\) — биномиальный коэффициент. Эквивалентный и более устойчивый в вычислениях подход — рекуррентное соотношение $$S(n,k) = k\cdot S(n-1,k) + S(n-1,k-1)$$ с начальными условиями \(S(0,0)=1\), \(S(n,0)=0\) при \(n>0\) и \(S(0,k)=0\) при \(k>0\). Наш калькулятор использует именно рекуррентную формулу, чтобы избежать потери точности при работе с числами с плавающей запятой. Полезные частные случаи: \(S(n,1)=1\), \(S(n,n)=1\) и \(S(n,2)=2^{n-1}-1\).
Разбор примера
Возьмём \(n=5\) и \(k=2\). По частному случаю получаем $$S(5,2)=2^{5-1}-1=16-1=15.$$ Рекуррентная формула подтверждает результат: $$S(5,2)=2\cdot S(4,2)+S(4,1)=2\cdot 7+1=15.$$ Значит, множество из 5 элементов можно разбить на две непустые группы ровно 15 способами.
Частые вопросы
Почему \(S(0,0)=1\)? По соглашению у пустого множества есть ровно одно разбиение на ноль частей — пустое разбиение.
Что будет, если k > n? Результат равен 0: каждое подмножество обязано быть непустым, а элементов слишком мало.
Как это связано с числами Белла? Если просуммировать \(S(n,k)\) по всем k от 0 до n, получится число Белла \(B(n)\) — общее количество разбиений множества из n элементов.
