Разбиение конечного множества образует любое семейство непустых и непересекающихся подмножеств его элементов, обычно называемых классами, когда каждый элемент является представителем своего класса. Каждый класс однозначно определяет состав его элементов, а порядок перечисления классов разбиений и элементов классов не имеет значения. Различными считаются разбиения, которые отличаются числом классов или составом хотя бы двух классов. Например, существует всего 5 различных разбиений трехэлементного множества {X,Y,Z} на классы. Эти разбиения перечислены ниже в таком порядке, когда число их классов не убывает:

Если зафиксировать количество классов, то в общем случае число разбиений множества из n элементов на m классов при любых n ≥ m ≥ 0 оказывается соответствующим по значениям для чисел Стирлинга второго рода. Формально эти числа определяют коэффициенты разложения степени n произвольной переменной Z по убывающим m-факториалам от Z при всех целых значениях m от 0 до n:

Zⁿ = (Z)₀ + (Z)₁ + ... + (Z)_m + ... + (Z)_n.

В этом разложении фигурные коэффициенты обозначают числа Стирлинга второго рода, а убывающие факториалы, перед которыми они стоят, определяют следующие произведения:

(Z)_m = Z(Z−1)(Z−2) … (Z−m+1).

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

Z³ = + Z + Z(Z - 1) + Z(Z - 1)(Z - 2).

Равенство левой и правой частей этого разложения, очевидно, будет достигнуто при следующих значениях коэффициентов, заданных соответствующими числами Стирлинга второго рода:

= 0; = 1; = 3; = 1;

В общем случае значения чисел Стирлинга второго рода при любых целых величинах n≥m≥0 можно записать в форме бесконечной нижнетреугольной матрицы, которая называется треугольником Стирлинга второго рода. Его начальный фрагмент, например, при 0≤n,m≤8 можно представить следующей таблицей:

По своей структуре эта таблица похожа на треугольник Паскаля. Ее внутренние элементы определяются по следующему мнемоническому правилу. Каждое число в любой строке n>0 и столбце m>0 равно сумме числа слева над ним и непосредственно над ним, которое умножено на m. Это правило иллюстрирует следующий пример для n=3 и m=2:

= + 2 = 1 + 2∙1 = 3.

В общем случае данное правило формально отражает следующее рекуррентное соотношение, которое справедливо для любых натуральных значений n≥m>0:

= + m

Граничные условия для этого рекуррентного соотношения определяют следующие значения чисел Стирлинга второго рода при m=0 и m=n:

= 0; = 1; = 1.

Следующий пример показывает использование рекуррентного соотношения и его граничных условий для рекурсивного вычисления значения числа Стирлинга второго рода при n=3 и m=2:

= + 2 = + + 2 = 0 + 1 + 2∙1 = 3.

Для рекурсивного вычисления значений чисел Стирлинга второго рода при больших величинах n и m также могут быть полезны следующие тождества:

= = n(n - 1)2 и = 2^n-1 - 1.

Следующий пример показывает, как с их помощью найти значение числа Стирлинга второго рода при n=6 и m=4 более коротким путем, чем по базовому рекуррентному соотношению:

= + 4 = + 3 + 4 = (2^4-1 - 1) + 34(4 - 1)2 + 45(5 -1 )2 = 65.

Как отмечалось выше, числа Стирлинга второго рода дают мощность множества разбиений n элементов на фиксированное число классов m≤n. Общее число всех разбиений n элементов без ограничения по числу классов определяется числом Белла, значение которого равно следующей сумме чисел Стирлинга второго рода:

B_n = + ... + + ... +

Принимая величину B₀ = 1, для вычисления значений чисел Белла можно использовать также следующую рекуррентную зависимость с биномиальными коэффициентами:

B_n = B₀ +  B₁+ ... + B_k+ ... + B_n

Результаты рекуррентных вычислений чисел Белла для всех значений n от 0 до 10 приведены в следующей таблице:

Из таблицы значений чисел Белла следует, что мощность множества разбиений быстро растет с увеличением количества элементов. Поэтому для решения разнообразных практических задач необходимо иметь комбинаторные алгоритмы, которые обеспечивают систематический перебор разбиений конечных множеств элементов любой мощности. По ряду причин перебор разбиений целесообразно производить в порядке минимального изменения состава их классов, когда любые 2 последовательных разбиения отличаются расположением только одного элемента в их классах. Очевидно, такое изменение следует считать минимальным. Например, в следующей последовательности все 5 разбиений множества {X,Y,Z} перечислены в порядке минимального изменения, а элементы, которые при этом переходят в другой класс, выделены подчеркиванием:

Для генерации разбиений в порядке минимального изменения были разработаны рекурсивный и итерационный алгоритмы, которые напоминают аналогичные методы транспозиции смежных элементов для перестановок. Они ориентированы на обработку любого множества натуральных чисел от 1 до n и обеспечивают систематическое перечисление всех его разбиений в порядке минимального изменения. При этом классы разбиений обычно упорядочивают по возрастанию величин своих минимальных элементов. С учетом указанного порядка перечисления классов, последовательность разбиений, например, числового множества {1,2,3}, которую формируют алгоритмы минимального изменения, имеет следующий вид:

В рекурсивном алгоритме минимального изменения такая последовательность, в общем случае, строится по следующему рекуррентному правилу. Пусть уже получен список всех разбиений множества из (n−1) натуральных чисел от 1 до (n−1), где классы упорядочены по возрастанию своих наименьших элементов, а любые последовательные разбиения минимально различны, в указанном выше смысле. Каждое разбиение этого списка дополняется одноэлементным классом {n}, а его классы дополняются элементом n. Причем указанные дополнения для нечетных по номеру разбиений производятся в порядке возрастания минимальных элементов классов и заканчиваются добавлением одноэлементного класса. Для четных по номеру разбиений такие же дополнения производятся в обратном порядке. В результате этой обработки получается уже список разбиений множества из n натуральных чисел, где все классы по-прежнему остаются упорядоченны по возрастанию своих наименьших элементов, а любые два соседних разбиения отличаются только расположением элемента n и, следовательно, минимально различны. Следующая диаграмма демонстрирует пример рассмотренного рекурсивного процесса, который начинается с одноэлементного множества {1} и завершается списком разбиений множества из трех чисел {1,2,3}. Для наглядности разбиения каждого уровня пронумерованы, а добавленные элементы выделены подчеркиванием, кроме того, стрелки указывают направление добавлений:

Для практической реализации рекурсивного алгоритма минимального изменения удобно задать каждое разбиение вектором наименьших элементов его классов. Тогда в общем случае любое разбиение множества последовательных натуральных чисел от 1 до n представляется вектором E(n) из n значений, где каждое значение E_j обозначает наименьший элемент класса, которому принадлежит элемент j. Такое соответствие можно формально задать следующим образом:

E_j = min i | E_j = E_i ; j = 1, ... n.

Для примера в следующей таблице перечислены все 5 последовательных разбиения множества {1,2,3} и соответствующие им векторы наименьших элементов их классов E(3):

В соответствие с рекурсивным алгоритмом каждый вектор наименьших элементов E(n) классов разбиения множества из n элементов расширяет соответствующий вектор E(n−1) значением E_n для добавленного элемента n. При этом нужно последовательно присвоить E_n все различные значения из вектора E(n−1), которые равны по величине своим индексам (j=E_j) и n. Для нечетных по номеру векторов E(n−1) такое присваивание делается в порядке возрастания индексов, что соответствует увеличению значений наименьших элементов классов разбиения, и завершается присваиванием E_n = n:

Например, вектор E(3) = (1,2,1), который соответствует разбиению { {1,3}, {2} }, с нечетным порядковым номером 5 расширяется в следующие различные варианты вектора E(4), образуя соответствующие им разбиения множества {1,2,3,4}:

Для четных по номеру векторов E(n−1) дополнение производится аналогично, но в порядке уменьшения значений наименьших элементов классов, и начинается присваиванием E_n = n:

Например, вектор E(3)=(1,2,2), который соответствует разбиению { {1}, {2 3} }, с четным порядковым номером 4 расширяется в следующие различные варианты вектора E(4), образуя соответствующие им разбиения множества {1,2,3,4}:

Несмотря на простоту, рассмотренный рекурсивный алгоритм нельзя признать экономичным, так как приходится последовательно порождать разбиения всех множеств с мощностями от 1 до n, хотя требуется получить разбиение только множества из n элементов. В этом отношении более привлекательным представляется итерационный алгоритм минимального изменения разбиений, который реализует систематический переход элементов между классами. При этом на каждой итерации очередное разбиение образуется из предыдущего переходом одного элемента в соседний класс слева или справа, если считать, что классы упорядочены по возрастанию значений своих наименьших элементов. Такой переход может изменять состав классов при сохранении их числа и приводить к удалению или образованию одноэлементного класса. В любом случае разбиения двух соседних итераций отличаются расположением только одного элемента в своих классах и, следовательно, минимально различны. В частности, следующая последовательность переходов элементов обеспечивает перечисление разбиений множества {1,2,3} в порядке минимального изменения, а стрелки указывают направление перехода элементов между классами:

В общем случае для систематической организации итерационного процесса важно установить правила перехода. Они должны обеспечивать выбор направления, элемента и классов перехода на каждой итерации при генерации разбиений любого множества последовательных чисел от 1 до n. Для формального описания этих правил удобно, как и раньше, задавать каждое разбиение вектором (E₁,…E_j,…,E_n) наименьших элементов его классов, где:

Для получения последующих разбиений на каждой итерации необходимо сначала выбрать для перехода наибольший по значению элемент m, который допустимо передвинуть вправо или влево в зависимости от установленного для него текущего направления перехода. Очевидно, переход влево любого элемента ограничен классом с наименьшим элементом 1, который сам не может быть влево или вправо. Переход вправо любого элемента j>1 ограничен классом, где он сам является наименьшим элементом. Поэтому правило выбора наименьшего элемента m для перехода на каждой итерации можно формально записать следующим образом:

Для удобства практической реализации этого правила целесообразно ввести знаковую функцию d(j) кодирования направления перехода каждого элемента j. Она должна принимать значение +1 или −1 при переходе элемента j вправо или влево, соответственно. Тогда в правиле выбора переходного элемента m можно исключить альтернативную проверку направления перехода и записать его следующим образом:

После выбора переходного элемента m нужно инвертировать направления перехода для всех элементов i>m. Такое преобразование можно условно записать следующим образом:

Наконец, требуется идентифицировать класс, куда следует передвинуть выбранный элемент m. Если для элемента m установлено направление перехода влево, то его необходимо передвинуть в соседний слева класс, наименьший элемент t которого определяется по следующему правилу:

Очевидно, что при переходе элемента m влево, между значениями t, m и Em должно быть выполнено следующее соотношение:

Если для выбранного элемента m установлено направление перехода вправо, то возможны два случая. В одном случае элемент m переходит в соседний справа класс, где наименьший элемент меньше, чем m. В другом случае, когда наименьший элемент соседнего справа класса больше, чем m, или элемент m принадлежит крайнему правому классу разбиения, из m должен быть образован одноэлементный класс {m}.

Оба указанных случая учитывает следующее формальное правило, которое идентифицирует наименьший элемент t класса, куда попадет элемент m после перехода вправо:

Очевидно, что при переходе элемента m вправо, между значениями t, m и E_m должно быть выполнено следующее соотношение:

Оба правила идентификации класса для перехода выбранного элемента m влево или вправо можно формально объединить, используя числовой код d(m) направления перехода элемента m. Такое комплексное правило автоматически учитывает направление перехода элемента m и идентифицирует наименьший элемент t класса для его перехода следующим образом:

Независимо от способа идентификации формальный переход выбранного элемента m в класс с наименьшим элементом t обеспечивает следующее присваивание:

В результате образуется очередное разбиение, которое отличается от разбиения предыдущей итерации только по составу двух классам, откуда и куда был передвинут элемент m. При этом в векторе наименьших элементов классов изменяется только значение E_m. Очевидно, что такое изменение разбиения является минимальным. Аналогичные итерации нужно продолжать до получения конечного разбиения, где для перехода формально выбирается элемент m=1, потому что все остальные элементы j>1 уже достигли своих крайних классов по установленному для них направлению перехода. Такое разбиение можно формально записать следующим образом:

d(→j)∙E_j = j или d(←j)∙E_j = −1 при j = 1, …, n.

Выполнение итераций рассмотренного итерационного алгоритма иллюстрируется в следующей таблице, где последовательные разбиения множества чисел {1,2,3} записаны в традиционном и векторном формате, а стрелки и знаки индексов обозначают направления перехода элементов: