Что такое число Стирлинга второго рода?
Число Стирлинга второго рода, обозначаемое \(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 элементов.
Таблица чисел Стирлинга второго рода S(n,k) для n от 0 до 10
Каждый элемент таблицы — это число способов разбить множество из n помеченных элементов на ровно k непустых непомеченных блоков. Таблица построена по рекуррентному соотношению \(S(n,k)=k\cdot S(n-1,k)+S(n-1,k-1)\), при \(S(0,0)=1\) и \(S(n,0)=S(0,n)=0\) для \(n\ge 1\). Пустые ячейки соответствуют \(k>n\), где S(n,k)=0. Последний столбец — сумма по строке, то есть число Белла B(n). Например, S(10,4) = 34105.
| n \ k | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | Сумма по строке 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 | ||
| 9 | 0 | 1 | 255 | 3025 | 7770 | 6951 | 2646 | 462 | 36 | 1 | 21147 | |
| 10 | 0 | 1 | 511 | 9330 | 34105 | 42525 | 22827 | 5880 | 750 | 45 | 1 | 115975 |
Проверка одного элемента по рекуррентному соотношению: \(S(6,3)=3\cdot S(5,3)+S(5,2)=3\cdot 25+15=90\). Всегда \(S(n,1)=1\), \(S(n,2)=2^{n-1}-1\), \(S(n,n-1)=\binom{n}{2}\) и \(S(n,n)=1\).
Основные термины и обозначения
- Разбиение множества
- Способ разбить множество на непустые попарно непересекающиеся подмножества (блоки), объединение которых даёт всё множество. Порядок блоков и порядок элементов внутри блока не имеют значения.
- Помеченные и непомеченные
- n элементов помечены (различимы, например 1, 2, …, n). k подмножеств не помечены: перестановка двух блоков даёт то же разбиение. Если бы блоки были помечены, количество было бы k!·S(n,k).
- Непустой блок
- Каждое из k подмножеств должно содержать хотя бы один элемент. Поэтому S(n,0)=0 при n ≥ 1 и S(n,k)=0 при k > n.
- Обозначение S(n,k)
- Число Стирлинга второго рода, также записываемое как \(\left\{ n \atop k \right\}\). Вычисляется по формуле \(S(n,k)=\frac{1}{k!}\sum_{j=0}^{k}(-1)^{j}\binom{k}{j}(k-j)^{n}\).
- Число Белла B(n)
- Общее число разбиений n-элементного множества на любое количество блоков: \(B(n)=\sum_{k=0}^{n}S(n,k)\). Первые значения: 1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975.
- Биномиальный коэффициент
- \(\binom{k}{j}=\frac{k!}{j!\,(k-j)!}\) — число способов выбрать j элементов из k. Он входит в формулу включения–исключения выше.
- Сюръекция
- Функция из n-множества на k-множество, при которой каждый элемент k-множества получает хотя бы один прообраз. Число таких функций равно \(k!\cdot S(n,k)\): разбиваем область определения на k блоков, затем назначаем блоки k значениям k! способами.
Числа второго и первого рода. Числа Стирлинга второго рода считают разбиения множества на k блоков. Числа Стирлинга первого рода, обозначаемые \(c(n,k)\) или \(\left[ n \atop k \right]\) (без знака), считают перестановки n элементов с ровно k циклами. Они подчиняются другому рекуррентному соотношению \(c(n,k)=(n-1)\,c(n-1,k)+c(n-1,k-1)\) и связаны с числами второго рода как взаимно обратные матрицы (с учётом знаков).