EssayAI
Блог
Блог
Естественные науки

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

8 ноября 2026Время чтения: 9 минут
#числа белла#комбинаторика#разбиения множества#числа стирлинга#алгоритмы
Числа Белла: разбиения множества и формула

Число Белла BnB_n показывает, сколькими способами можно разбить множество из nn различных элементов на непустые группы. Каждый элемент попадает ровно в одну группу, а порядок самих групп не важен. Например, трёх студентов можно распределить по учебным командам пятью способами, если не различать команды по названиям и допускать любое их количество.

Попробуйте калькулятор: выберите число элементов и сравните столбцы для разного числа групп. Их сумма и есть число Белла. Ниже разберём, почему формула считает каждое разбиение ровно один раз и как реализовать её в программе.

Что считается разбиением множества

Пусть множество состоит из элементов {1,2,3}\{1,2,3\}. Разбиение - это набор его непустых подмножеств, называемых блоками, которые не пересекаются и вместе содержат все элементы. Объекты различимы: переставить элементы 2 и 3 между группами может означать получить другое разбиение. Но блоки не имеют имён, поэтому их перестановка нового варианта не создаёт.

Все пять разбиений тройки выглядят так:

  1. {{1,2,3}}\{\{1,2,3\}\} - один блок;
  2. {{1,2},{3}}\{\{1,2\},\{3\}\};
  3. {{1,3},{2}}\{\{1,3\},\{2\}\};
  4. {{2,3},{1}}\{\{2,3\},\{1\}\} - три способа получить два блока;
  5. {{1},{2},{3}}\{\{1\},\{2\},\{3\}\} - три блока.

Значит, B3=1+3+1=5B_3=1+3+1=5. Записи {{1,2},{3}}\{\{1,2\},\{3\}\} и {{3},{2,1}}\{\{3\},\{2,1\}\} описывают один и тот же вариант. Важно отличать разбиение от выбора одного подмножества: здесь нужно распределить все элементы. О числе возможных выборов отдельного подмножества рассказано в статье о числе подмножеств множества.

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

На видео слева исходная пара лежит в одном блоке, а справа - в двух. В первом случае для нового элемента есть два места: общий блок или новый отдельный блок. Во втором случае мест три: любой из двух старых блоков или новый. Если затем удалить элемент 3 из любого результата, исходное разбиение пары восстановится однозначно. Поэтому варианты не повторяются.

Первые числа Белла

Первые значения при nn от 0 до 8 равны:

nn012345678
BnB_n112515522038774140

Значение B0=1B_0=1 может показаться странным: ведь элементов нет. Но есть ровно одно разбиение пустого множества - пустой набор блоков. В нём нет пустого блока: блоков вообще нет. Это соглашение естественно для рекуррентных формул и соответствует обычному правилу считать один способ ничего не выбрать. Определение, таблица и формулы приведены в справочнике NIST DLMF.

Рост очень быстр: уже для десяти объектов есть B10=115975B_{10}=115975 разбиений. Поэтому ручное перечисление удобно для проверки малых примеров, но для больших входов лучше считать значения динамически. Число вариантов говорит о размере пространства поиска, но само по себе не находит лучшее разбиение по заданному критерию.

Рекуррентная формула: выделяем один блок

Зафиксируем элемент n+1n+1 и посмотрим на блок, в котором он находится. Пусть вне этого блока лежат ровно kk из остальных nn элементов. Выбрать их можно (nk)\binom{n}{k} способами, а затем разбить выбранное множество на группы - BkB_k способами. Все остальные элементы автоматически присоединяются к блоку элемента n+1n+1.

По правилу суммы получаем:

Bn+1=∑k=0n(nk)Bk,B0=1.B_{n+1}=\sum_{k=0}^{n}\binom{n}{k}B_k,\qquad B_0=1.

Здесь kk может быть равен нулю: тогда все элементы попадают в один блок. При k=nk=n выделенный элемент образует отдельный блок. Эти случаи включены в сумму, а разбиения при разных kk не совпадают. Обоснование использует правила суммы и произведения в комбинаторике.

Например, для четырёх элементов:

B4=(30)B0+(31)B1+(32)B2+(33)B3=1+3+6+5=15.B_4=\binom30B_0+\binom31B_1+\binom32B_2+\binom33B_3=1+3+6+5=15.

Числа 1, 3, 6 и 5 в этой сумме группируют варианты по тому, сколько элементов осталось вне блока с четвёртым элементом. Это не распределение по общему числу блоков: для него нужна следующая таблица.

Связь с числами Стирлинга второго рода

Обозначим через S(n,k)S(n,k) количество разбиений nn различных элементов ровно на kk непустых блоков. Тогда число Белла получается суммированием по допустимому количеству блоков:

Bn=∑k=0nS(n,k).B_n=\sum_{k=0}^{n}S(n,k).

Для четырёх элементов распределение равно S(4,1)=1S(4,1)=1, S(4,2)=7S(4,2)=7, S(4,3)=6S(4,3)=6, S(4,4)=1S(4,4)=1. Сумма 1+7+6+1=151+7+6+1=15 совпадает с вычислением через рекуррентную формулу Белла.

Столбцы числа разбиений четырёх элементов на одну, две, три и четыре группы: 1, 7, 6 и 1, всего 15
Столбцы числа разбиений четырёх элементов на одну, две, три и четыре группы: 1, 7, 6 и 1, всего 15

Почему S(4,2)=7S(4,2)=7? Один блок может состоять из одного элемента: для него есть четыре выбора. Либо оба блока содержат по два элемента: выбор пары даёт шесть вариантов, но каждое разбиение учтено дважды, поэтому остаётся три. Вместе получается семь. Для трёх блоков достаточно выбрать пару из четырёх элементов, то есть получить шесть вариантов; остальные два элемента будут одиночными блоками.

Не путайте два рода чисел Стирлинга. Второй род считает разбиения на блоки, а числа Стирлинга первого рода связаны с циклами перестановок. Название похоже, но объекты подсчёта различаются.

Пример: пять участников и три команды

Пусть пять разных участников нужно разделить ровно на три непустые команды без названий. Возможны только два типа размеров команд: 3,1,13,1,1 или 2,2,12,2,1. В первом случае выбираем тройку из пяти участников: получаем (53)=10\binom53=10 вариантов. Оставшиеся два участника автоматически образуют отдельные команды, и менять эти команды местами не нужно.

Во втором случае сначала выбираем одиночного участника пятью способами. Из оставшихся четырёх выбираем пару шестью способами; последняя пара определяется автоматически. Но каждая пара команд при таком выборе появляется дважды, поскольку в качестве первой можно было выбрать любую из двух пар. Поэтому этот тип даёт 5⋅6/2=155\cdot6/2=15 вариантов. Всего 10+15=2510+15=25, то есть S(5,3)=25S(5,3)=25.

Пример показывает, когда нельзя просто сложить числа для всех возможных количеств команд: условие задачи фиксирует именно три. Если бы команд могло быть любое число от одной до пяти, следовало бы добавить и все остальные допустимые случаи. Именно это делает сумма чисел Стирлинга, дающая B5=52B_5=52.

Как вычислять числа программно

Таблицу второго рода удобно строить по строкам. Для нового элемента есть два взаимоисключающих случая: он либо входит в один из kk уже существующих блоков, либо образует новый блок, а остальные элементы разбиты на k−1k-1 блоков. Поэтому

S(n,k)=kS(n−1,k)+S(n−1,k−1).S(n,k)=kS(n-1,k)+S(n-1,k-1).

Начинают с S(0,0)=1S(0,0)=1 и считают отсутствующие значения нулями. Строка для n=3n=3 равна 0,1,3,10,1,3,1. По ней, например, S(4,2)=2⋅3+1=7S(4,2)=2\cdot3+1=7: шесть разбиений получаются добавлением элемента в один из двух блоков, ещё одно - созданием отдельного блока.

Псевдокод хранит только предыдущую строку:

строка = [1]
для i от 1 до n:
    новая = массив из i + 1 нулей
    для k от 1 до i:
        новая[k] = k * строка[k] + строка[k - 1]
        если строка[k] отсутствует, считать её нулём
    строка = новая
ответ = сумма элементов строки

Алгоритм выполняет порядка n2n^2 арифметических операций и хранит порядка nn чисел. Это оценка числа операций и ячеек; сами числа растут, поэтому стоимость арифметики и память в битах увеличиваются. В языках с ограниченной точностью целых для больших nn нужны целые произвольной длины. Калькулятор выше ограничен десятью элементами, чтобы значения оставались небольшими и график легко читался.

Где возникает такая модель

Разбиения появляются при группировке объектов без заранее заданных меток групп: например, при переборе возможных кластеризаций небольшого набора документов или распределений участников по непустым командам. Если же команды называются «А», «Б» и «В», обмен состава команд меняет результат, и непосредственно число Белла уже не отвечает на вопрос.

Другой взгляд: каждое разбиение задаёт отношение эквивалентности - два элемента эквивалентны, если находятся в одном блоке. И наоборот, классы любого отношения эквивалентности образуют разбиение. Поэтому число Белла также считает такие отношения на конечном множестве. Подробнее о связи классов и фактор-множества - в статье об отношении эквивалентности.

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

Для практического перебора можно представлять разбиение списком блоков. Начав с пустого набора, добавляйте очередной объект либо в каждый уже имеющийся блок, либо в новый блок. Важно не переставлять блоки при построении одного и того же результата: например, хранить их в порядке появления первого элемента. Такой способ позволяет получить сами варианты, тогда как рекурсия выше хранит только их количества. Перебор быстро становится дорогим именно потому, что вывод содержит BnB_n вариантов; подсчёт таблицы обходит необходимость создавать каждый из них.

Частые ошибки

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

FAQ

Чему равно число Белла для пяти элементов?

B5=52B_5=52. Это общее число разбиений пяти различимых элементов на любое число непустых неупорядоченных блоков.

Сколько разбиений пяти элементов имеют ровно три блока?

S(5,3)=25S(5,3)=25. Это только часть из 52 разбиений: остальные имеют другое число блоков.

Почему B0B_0 равно единице?

Пустой набор блоков единственным способом покрывает пустое множество. Он не содержит пустых блоков и служит начальным случаем рекурсии.

Коротко

Числа Белла считают разбиения различимых элементов на непустые неупорядоченные группы. Их можно получить суммой чисел Стирлинга второго рода или рекурсией с выделенным блоком. Для трёх элементов получается пять разбиений, для четырёх - пятнадцать; условия задачи определяют, подходит ли эта модель.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

Разбиение числа на слагаемые: подсчёт и алгоритм

Разбиение числа на слагаемые: подсчёт и алгоритм

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

8 ноября 20269 минут
Задача о восьми ферзях: решение и алгоритм

Задача о восьми ферзях: решение и алгоритм

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

8 ноября 20268 минут
Алгоритм LZ77: сжатие с помощью ссылок назад

Алгоритм LZ77: сжатие с помощью ссылок назад

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

8 ноября 20268 минут
Числа трибоначчи: формула и примеры вычисления

Числа трибоначчи: формула и примеры вычисления

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

8 ноября 20269 минут
Чётность подстановки: инверсии и знак

Чётность подстановки: инверсии и знак

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

8 ноября 20268 минут
Дерево двоичного поиска: построение и операции

Дерево двоичного поиска: построение и операции

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

8 ноября 20268 минут