Математика / Графы, логика

Числа Стирлинга второго рода: разбиение на группы

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

Опубликовано: 16 октября 2026 г.Обновлено: 16 октября 2026 г.

Формула

$$S(n,k)=kS(n-1,k)+S(n-1,k-1)$$

Схема Таблица разбиений на непустые группы

Выделено значение S(5,3)=25, полученное из предыдущей строки.

Обозначения

$S(n,k)$: число разбиений на непустые неименованные блоки, безразмерная величина
$n$: число различных элементов, безразмерная величина
$k$: число непустых групп, безразмерная величина

Условия применения

Параметры n и k целые неотрицательные. Группы попарно не пересекаются и вместе содержат все элементы; каждая группа непуста. Начальные значения: S(0,0)=1, S(n,0)=0 при n>0, S(n,k)=0 при k>n. Рекурсия используется при n≥1 и k≥1.

Ограничения

Формула не относится к разбиениям числа n на слагаемые: здесь различимы сами объекты. Она не фиксирует размеры групп. Если группы подписаны, разбиение нужно дополнительно сопоставить названиям. Числа Стирлинга первого рода считают циклы перестановок и являются другой последовательностью.

Подробное объяснение

Рассмотрим последний, n-й, элемент. В готовом разбиении он либо образует отдельную группу из одного элемента, либо лежит вместе хотя бы с одним из предыдущих n−1 элементов. Эти случаи не пересекаются и исчерпывают все возможности.

Если последний элемент стоит отдельно, остальные надо разбить на k−1 непустых групп. Это даёт S(n−1,k−1) вариантов. Новая одноэлементная группа не имеет номера, поэтому дополнительного множителя k в этом случае нет.

Если отдельной группы нет, удаление последнего элемента оставляет k непустых групп. Предыдущие элементы можно разбить S(n−1,k) способами, а новый элемент поместить в любую из k уже существующих групп. Получаем kS(n−1,k), после чего складываем два случая.

Начальные значения задают края таблицы: один непустой набор образует одну группу единственным способом, а n объектов разбиваются на n групп только как n одиночек. Поэтому S(n,1)=S(n,n)=1 при n≥1. Все внутренние значения удобно находить строка за строкой.

Если группы получают различные метки, каждое неименованное разбиение даёт k! назначений меток. Число сюръекций из n элементов в k меток равно k!S(n,k). Обычное kⁿ включает также назначения с пустыми группами, поэтому без дополнительного условия его использовать нельзя.

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

Проверьте различимость объектов и отсутствие названий у групп; порядок внутри блока не должен учитываться.
Запишите n и k, отдельно проверьте невозможный случай k>n и требование непустоты всех групп.
Начните таблицу с S(0,0)=1 и нулей за допустимым треугольником; вычисляйте строки по рекурсии.
Если в задаче группы всё же подписаны, умножьте полученный результат на k! и объясните назначение меток.

Историческая справка

Название связано с Джеймсом Стирлингом и развитием алгебры конечных разностей. Его Methodus Differentialis 1730 года посвящена рядам, суммированию и интерполяции; исторический очерк Университета Сент-Эндрюс рассматривает эту работу в контексте вычислительной математики XVIII века. В современной комбинаторике различают два рода чисел Стирлинга: коэффициенты с циклической интерпретацией и числа разбиений множества на непустые блоки. NIST DLMF явно разделяет эти определения и приводит рекуррентные соотношения. Нынешнее доказательство через положение последнего элемента удобно для учебного изложения и программирования динамической таблицы. Его не следует смешивать со знаменитой приближённой формулой Стирлинга для факториала: совпадение имени не делает эти формулы одной и той же задачей.

Историческая линия формулы

Общепринятое имя чисел связано со Стирлингом и алгебраической традицией XVIII века. На странице рассматриваются именно числа второго рода с современной интерпретацией разбиений множества; это отдельный объект, отличный от приближения факториала и чисел первого рода.

Пример

Четыре различных задания А, Б, В, Г нужно разделить на две непустые неименованные группы. Для трёх элементов S(3,2)=3: отдельным может быть любой из трёх, а остальные образуют пару; S(3,1)=1. Рекурсия даёт S(4,2)=2S(3,2)+S(3,1)=2·3+1=7. Проверим другим способом: выбираем непустое собственное подмножество из четырёх объектов — 2⁴−2=14 вариантов. Оно и его дополнение задают одну и ту же пару неименованных групп, поэтому делим на 2 и получаем 7. Если группы назвать «утро» и «вечер», назначения меток различаются, и ответ станет 7·2!=14.

Частая ошибка

Не считайте группы пронумерованными, если в условии они не имеют названий. Не допускайте пустые блоки: kⁿ описывает другое множество назначений. Не путайте числа первого и второго рода. Не делите произвольное число упорядоченных раскладок на k! без проверки, что каждая конфигурация посчитана одинаковое число раз.

Практика

Задачи с решением

Пять объектов, три группы

Условие. Найдите S(5,3), если S(4,3)=6 и S(4,2)=7.

Решение. S(5,3)=3S(4,3)+S(4,2)=3·6+7=25.

Ответ. 25 разбиений

Шесть объектов, две группы

Условие. Разбейте шесть различных объектов на две непустые неименованные группы.

Решение. Из 2⁶ подмножеств исключаем пустое и полное. Каждая пара дополнений посчитана дважды: (64−2)/2=31.

Ответ. 31 разбиение

Дополнительные источники

https://dlmf.nist.gov/26.8
https://mathshistory.st-andrews.ac.uk/Biographies/Stirling/

Связанные формулы

Математика

Число сочетаний без повторений

$C_n^k=\binom nk=\frac{n!}{k!(n-k)!}$

Формула описывает прием «неупорядоченный выбор» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Правило произведения в комбинаторике

$N=m_1m_2\cdots m_k$

Формула описывает прием «умножение последовательных шагов» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.

Математика

Рекуррентная формула чисел Фибоначчи

$F_0=0,\quad F_1=1,\quad F_n=F_{n-1}+F_{n-2}$

Формула описывает прием «рекуррентное сложение» для подсчета конечных объектов без полного перебора. Она фиксирует, что именно считается: случаи, шаги, группы, пересечения, рекуррентные члены или пары вершин, и помогает избежать двойного счета.