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

Число Белла показывает, сколькими способами можно разбить множество из различных элементов на непустые группы. Каждый элемент попадает ровно в одну группу, а порядок самих групп не важен. Например, трёх студентов можно распределить по учебным командам пятью способами, если не различать команды по названиям и допускать любое их количество.
Попробуйте калькулятор: выберите число элементов и сравните столбцы для разного числа групп. Их сумма и есть число Белла. Ниже разберём, почему формула считает каждое разбиение ровно один раз и как реализовать её в программе.
Что считается разбиением множества
Пусть множество состоит из элементов . Разбиение - это набор его непустых подмножеств, называемых блоками, которые не пересекаются и вместе содержат все элементы. Объекты различимы: переставить элементы 2 и 3 между группами может означать получить другое разбиение. Но блоки не имеют имён, поэтому их перестановка нового варианта не создаёт.
Все пять разбиений тройки выглядят так:
- - один блок;
- ;
- ;
- - три способа получить два блока;
- - три блока.
Значит, . Записи и описывают один и тот же вариант. Важно отличать разбиение от выбора одного подмножества: здесь нужно распределить все элементы. О числе возможных выборов отдельного подмножества рассказано в статье о числе подмножеств множества.
На видео слева исходная пара лежит в одном блоке, а справа - в двух. В первом случае для нового элемента есть два места: общий блок или новый отдельный блок. Во втором случае мест три: любой из двух старых блоков или новый. Если затем удалить элемент 3 из любого результата, исходное разбиение пары восстановится однозначно. Поэтому варианты не повторяются.
Первые числа Белла
Первые значения при от 0 до 8 равны:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | |
|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 5 | 15 | 52 | 203 | 877 | 4140 |
Значение может показаться странным: ведь элементов нет. Но есть ровно одно разбиение пустого множества - пустой набор блоков. В нём нет пустого блока: блоков вообще нет. Это соглашение естественно для рекуррентных формул и соответствует обычному правилу считать один способ ничего не выбрать. Определение, таблица и формулы приведены в справочнике NIST DLMF.
Рост очень быстр: уже для десяти объектов есть разбиений. Поэтому ручное перечисление удобно для проверки малых примеров, но для больших входов лучше считать значения динамически. Число вариантов говорит о размере пространства поиска, но само по себе не находит лучшее разбиение по заданному критерию.
Рекуррентная формула: выделяем один блок
Зафиксируем элемент и посмотрим на блок, в котором он находится. Пусть вне этого блока лежат ровно из остальных элементов. Выбрать их можно способами, а затем разбить выбранное множество на группы - способами. Все остальные элементы автоматически присоединяются к блоку элемента .
По правилу суммы получаем:
Здесь может быть равен нулю: тогда все элементы попадают в один блок. При выделенный элемент образует отдельный блок. Эти случаи включены в сумму, а разбиения при разных не совпадают. Обоснование использует правила суммы и произведения в комбинаторике.
Например, для четырёх элементов:
Числа 1, 3, 6 и 5 в этой сумме группируют варианты по тому, сколько элементов осталось вне блока с четвёртым элементом. Это не распределение по общему числу блоков: для него нужна следующая таблица.
Связь с числами Стирлинга второго рода
Обозначим через количество разбиений различных элементов ровно на непустых блоков. Тогда число Белла получается суммированием по допустимому количеству блоков:
Для четырёх элементов распределение равно , , , . Сумма совпадает с вычислением через рекуррентную формулу Белла.

Почему ? Один блок может состоять из одного элемента: для него есть четыре выбора. Либо оба блока содержат по два элемента: выбор пары даёт шесть вариантов, но каждое разбиение учтено дважды, поэтому остаётся три. Вместе получается семь. Для трёх блоков достаточно выбрать пару из четырёх элементов, то есть получить шесть вариантов; остальные два элемента будут одиночными блоками.
Не путайте два рода чисел Стирлинга. Второй род считает разбиения на блоки, а числа Стирлинга первого рода связаны с циклами перестановок. Название похоже, но объекты подсчёта различаются.
Пример: пять участников и три команды
Пусть пять разных участников нужно разделить ровно на три непустые команды без названий. Возможны только два типа размеров команд: или . В первом случае выбираем тройку из пяти участников: получаем вариантов. Оставшиеся два участника автоматически образуют отдельные команды, и менять эти команды местами не нужно.
Во втором случае сначала выбираем одиночного участника пятью способами. Из оставшихся четырёх выбираем пару шестью способами; последняя пара определяется автоматически. Но каждая пара команд при таком выборе появляется дважды, поскольку в качестве первой можно было выбрать любую из двух пар. Поэтому этот тип даёт вариантов. Всего , то есть .
Пример показывает, когда нельзя просто сложить числа для всех возможных количеств команд: условие задачи фиксирует именно три. Если бы команд могло быть любое число от одной до пяти, следовало бы добавить и все остальные допустимые случаи. Именно это делает сумма чисел Стирлинга, дающая .
Как вычислять числа программно
Таблицу второго рода удобно строить по строкам. Для нового элемента есть два взаимоисключающих случая: он либо входит в один из уже существующих блоков, либо образует новый блок, а остальные элементы разбиты на блоков. Поэтому
Начинают с и считают отсутствующие значения нулями. Строка для равна . По ней, например, : шесть разбиений получаются добавлением элемента в один из двух блоков, ещё одно - созданием отдельного блока.
Псевдокод хранит только предыдущую строку:
строка = [1]
для i от 1 до n:
новая = массив из i + 1 нулей
для k от 1 до i:
новая[k] = k * строка[k] + строка[k - 1]
если строка[k] отсутствует, считать её нулём
строка = новая
ответ = сумма элементов строки
Алгоритм выполняет порядка арифметических операций и хранит порядка чисел. Это оценка числа операций и ячеек; сами числа растут, поэтому стоимость арифметики и память в битах увеличиваются. В языках с ограниченной точностью целых для больших нужны целые произвольной длины. Калькулятор выше ограничен десятью элементами, чтобы значения оставались небольшими и график легко читался.
Где возникает такая модель
Разбиения появляются при группировке объектов без заранее заданных меток групп: например, при переборе возможных кластеризаций небольшого набора документов или распределений участников по непустым командам. Если же команды называются «А», «Б» и «В», обмен состава команд меняет результат, и непосредственно число Белла уже не отвечает на вопрос.
Другой взгляд: каждое разбиение задаёт отношение эквивалентности - два элемента эквивалентны, если находятся в одном блоке. И наоборот, классы любого отношения эквивалентности образуют разбиение. Поэтому число Белла также считает такие отношения на конечном множестве. Подробнее о связи классов и фактор-множества - в статье об отношении эквивалентности.
Прежде чем применять формулу, уточните условия: различимы ли объекты, можно ли оставлять группы пустыми, фиксировано ли количество групп и имеют ли они имена. Например, ограничение на размер команд исключает часть разбиений, а требование ровно трёх команд приводит к вместо полной суммы .
Для практического перебора можно представлять разбиение списком блоков. Начав с пустого набора, добавляйте очередной объект либо в каждый уже имеющийся блок, либо в новый блок. Важно не переставлять блоки при построении одного и того же результата: например, хранить их в порядке появления первого элемента. Такой способ позволяет получить сами варианты, тогда как рекурсия выше хранит только их количества. Перебор быстро становится дорогим именно потому, что вывод содержит вариантов; подсчёт таблицы обходит необходимость создавать каждый из них.
Частые ошибки
- Считать порядок блоков. Перестановка блоков не создаёт новое разбиение; для упорядоченных блоков нужна другая модель.
- Включать пустые блоки. В разбиении каждый блок непуст; при есть одно разбиение без блоков.
- Подменять значением . Первое допускает все возможные количества блоков, второе фиксирует .
- Путать разбиение множества с разбиением числа. При разбиении множества элементы различимы, поэтому состав каждой группы важен.
FAQ
Чему равно число Белла для пяти элементов?
. Это общее число разбиений пяти различимых элементов на любое число непустых неупорядоченных блоков.
Сколько разбиений пяти элементов имеют ровно три блока?
. Это только часть из 52 разбиений: остальные имеют другое число блоков.
Почему равно единице?
Пустой набор блоков единственным способом покрывает пустое множество. Он не содержит пустых блоков и служит начальным случаем рекурсии.
Коротко
Числа Белла считают разбиения различимых элементов на непустые неупорядоченные группы. Их можно получить суммой чисел Стирлинга второго рода или рекурсией с выделенным блоком. Для трёх элементов получается пять разбиений, для четырёх - пятнадцать; условия задачи определяют, подходит ли эта модель.
Читайте также

Разбиение числа на слагаемые: подсчёт и алгоритм
Разбиение числа на слагаемые без учёта порядка: примеры, отличие от упорядоченных сумм, рекуррентная формула и алгоритм динамического программирования.

Задача о восьми ферзях: решение и алгоритм
Задача о восьми ферзях: готовая расстановка, проверка диагоналей и перебор с возвратом. Разбираем 92 решения, симметрии и обобщение на доску размера n.

Алгоритм LZ77: сжатие с помощью ссылок назад
Алгоритм LZ77 на пошаговом примере: как скользящее окно находит повторы, что означают расстояние и длина, как работает перекрытие и от чего зависит размер результата.

Числа трибоначчи: формула и примеры вычисления
Числа трибоначчи: три начальных значения, рекуррентная формула и расчёт по шагам. Как последовательность считает пути по ступенькам и как написать эффективный алгоритм.

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

Дерево двоичного поиска: построение и операции
Дерево двоичного поиска: как устроены узлы, как построить BST по ключам, выполнить обход и удалить элемент, от чего зависит высота и сложность операций.