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

Числа Белла: все разбиения множества на группы

Число Белла считает все способы разделить различимые элементы на непустые непересекающиеся группы. Число групп заранее не задано, их порядок и порядок элементов внутри группы не учитываются.

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

Формула

B_n=\sum_{k=0}^{n}S(n,k),\qquad B_0=1

Схема Пять разбиений трёх объектов

Один, два или три блока: 1 + 3 + 1 = 5.

Обозначения

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

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

Элементы различимы, каждый входит ровно в одну группу, пустые группы не создаются. Две записи с одинаковым набором групп считаются одним разбиением. Для n=0 принимают одно пустое разбиение; для n>0 слагаемое S(n,0) равно нулю.

Ограничения

Если группы имеют номера или названия, каждое разбиение на k групп необходимо дополнительно разметить k! способами. Ограничение размеров команд меняет подсчёт. Число Белла не равно числу разбиений целого числа: здесь различаются сами объекты, а не только размеры частей.

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

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

На трёх элементах A, B, C есть одна общая группа, три разбиения на пару и одиночный элемент и одно разбиение на три одиночных элемента. Итого B₃=1+3+1=5. Перестановка фигурных скобок не создаёт нового варианта: {A,B}|{C} и {C}|{B,A} описывают одну группировку.

Для вычисления длинной последовательности удобно пользоваться рекуррентным правилом Bₙ₊₁=Σ C(n,j)Bⱼ, где j меняется от нуля до n. Выберем j элементов, не попавших в группу нового элемента. Их можно разбить Bⱼ способами; остальные вместе с новым элементом образуют одну фиксированную группу.

Числа быстро растут: уже для пяти объектов вариантов больше пятидесяти. Это объясняет, почему полный перебор группировок перестаёт быть удобным даже для небольших наборов. Рекурсия считает количество, но сама по себе не выбирает лучшую группировку и не оценивает её качество.

При проверке полезны границы: для n≥1 существуют вариант «все вместе» и вариант «каждый отдельно». Однако при n=1 они совпадают, поэтому B₁=1. Такое исключение показывает, почему нельзя механически складывать словесно разные описания без проверки их содержания.

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

Проверьте, различаются ли исходные объекты и можно ли свободно менять число непустых групп.
Составьте строку S(n,k) для всех k от нуля до n; пустые группы в подсчёт включать нельзя.
Сложите числа одной строки Стирлинга, не умножая их на факториал числа неназванных групп.
Для малого n перечислите разбиения вручную и сравните сумму с количеством разных группировок.

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

Числа Белла названы в честь Эрика Темпла Белла и входят в современную комбинаторную теорию разбиений множеств. В справочнике NIST DLMF им посвящён отдельный раздел, расположенный рядом с числами Стирлинга. Такое расположение отражает содержательную связь: числа Стирлинга уточняют подсчёт по числу блоков, а числа Белла суммируют эти уточнения. В университетской и справочной литературе XX–XXI веков эта последовательность используется как стандартный пример подсчёта неупорядоченных структур. Важно отличать название последовательности от утверждения о первом появлении каждой её интерпретации. Задачи группировки, отношения эквивалентности и рекуррентные таблицы дают разные входы в одну теорию; здесь не приписывается Беллу изобретение всех способов разбивать множество.

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

Название «числа Белла» относится к последовательности количеств разбиений множества. Представление через сумму чисел Стирлинга следует из разделения разбиений по числу блоков; это стандартное комбинаторное тождество, а не отдельный закон о случайном выборе команд.

Пример

Четырёх участников A, B, C, D нужно разбить на любое число неназванных команд. Все участники должны попасть в команду, одиночные команды допустимы. Для n=4 строка чисел Стирлинга по k=1,2,3,4 равна 1,7,6,1. Получаем B₄ = 1 + 7 + 6 + 1 = 15 вариантов. Проверим средние слагаемые: две команды дают четыре выбора одиночного участника и три разбиения на пары, то есть 7; три команды получаются выбором одной пары из четырёх участников, то есть C(4,2)=6. Крайние варианты — все вместе и все отдельно. Ответ: 15 группировок, без единиц измерения. Перестановка команд местами ответ не увеличивает.

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

Не заменяйте сумму одним S(n,k): тогда число групп окажется фиксированным. Не умножайте итог на n!: это внесёт порядок, которого нет в условии. Не считайте одинаковыми разбиения с одинаковыми размерами, но разным составом групп. Не добавляйте пустую команду: её наличие не является новым разбиением.

Практика

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

Пять элементов

Условие. Найдите B₅, если S(5,k) при k = 1…5 равно 1,15,25,10,1.

Решение. Суммируем все допустимые числа групп: B₅ = 1 + 15 + 25 + 10 + 1 = 52.

Ответ. 52 разбиения

Два элемента

Условие. Перечислите все разбиения {A,B}.

Решение. Варианты: {A,B} и {A}|{B}. Порядок двух одиночных групп не учитываем.

Ответ. 2 разбиения

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

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

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

Математика

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

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

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

Математика

Правило суммы в комбинаторике

$N=m_1+m_2+\cdots+m_k$

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

Математика

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

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

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