Калькулятор чисел Стирлинга второго рода S(n,k)

Калькулятор чисел Стирлинга второго рода S(n,k)

Растущий AI Skill PRO

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

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

S(n,k)=1k!∑j=0k(−1)j(kj)(k−j)nS\!\left(\text{n},\,\text{k}\right) = \frac{1}{\text{k}!}\sum_{j=0}^{\text{k}} (-1)^{j}\binom{\text{k}}{j}\left(\text{k}-j\right)^{\text{n}}
Статистика использования

Реклама

Результаты

Число Стирлинга второго рода S(5, 2)
15
способов разбить различимые элементы на непустые подмножества (Элементы: 5 · Подмножества: 2)
n (размер множества) 5
k (подмножества) 2
Обозначение S(n, k)

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

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

Число Стирлинга второго рода, обозначаемое \(S(n,k)\), показывает, сколькими способами можно разбить множество из n различных (помеченных) элементов ровно на k непустых неупорядоченных подмножеств. Это одна из ключевых величин комбинаторики: она возникает в задачах о разбиениях множеств, о сюръекциях и тесно связана с числами Белла. Инструмент относится к чистой математике и работает одинаково в любой стране — никаких национальных особенностей здесь нет.

Четыре помеченных шара, разложенных в два непомеченных ящика — пример разбиения множества
\(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(n,k)\), где каждое получается из двух значений над ним.

Частые вопросы

Почему \(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)\) и связаны с числами второго рода как взаимно обратные матрицы (с учётом знаков).

Последнее обновление:

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

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