Разбиением натурального числа n называется его представление в виде суммы целых положительных слагаемых:

, где p_i>0

Например, одним из возможных вариантов разбиения числа 7 на 4 слагаемых является следующая сумма:

Порядок перечисления слагаемых разбиения значения не имеет. Поэтому, например, следующие 2 разбиения числа 7 на 3 слагаемых являются эквивалентными комбинаторными объектами:

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

В частности, представленное выше разбиение числа 7 на 3 слагаемых обычно записывается в любом из следующих 2-х вариантах:

или

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

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

В этом соотношении предполагается, что все аргументы в правой части должны быть неотрицательны и считается, что Р(0)=1;

Следующий пример демонстрирует последовательность выполнений первых 8-ми натуральных чисел:

Алгоритмически более сложной комбинаторной проблемой является задача математического перечисления всех разбиений любого заданного натурального числа. Для решения этой задачи обычно применяется либо алгоритм Гиндербурга, открытый в 1778 году, либо более современный и значительно более эффективный алгоритм Эрлиха.

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

На начальном шаге этого алгоритма выбирается тривиальное разбиение, состоящее только из одного слагаемого, равного n:

У последующих разбиений число слагаемых l последовательно растёт (или по крайней мере не убывает), а сами слагаемые записываются в порядке неубывания их величин:

Каждое очередное разбиение конструируется по текущему следующем образом. Слагаемые текущего разбиения нужно просмотреть справа налево (в направлении от p_l к p₁) с целью найти самое правое слагаемое p_i, для которого выполняется неравенство:

Если такое слагаемое p_i существует в текущем разбиении, то значения всех слагаемых p_j, начиная с p_i до последнего слагаемого (p_l-1), нужно увеличить на 1:

для всех

Иначе, когда последнее слагаемое p_l не превосходит остальные по величине больше, чем на 1, тогда значения всех слагаемых принимаются равными 1, и затем длина разбиения увеличивается на 1:

и

В любом случае значение последнего слагаемого p_l по формуле:

Например, при генерации разбиений числа 7 на 10-м шаге получено текущее разбиение из 4-х слагаемых (l=4):

В этом разбиении последнее слагаемое р₄ равно 3. Его значение больше на 2 слагаемого р₂, равного 1. Поэтому в следующем разбиении слагаемое р₂ и р₃ будут равны 2. Значение последнего слагаемого р₄ вычисляется по остаточной формуле и будет также равно 2. Таким образом, очередным разбиением будет разбиение той же длины, на следующее в лексиграфическом порядке слагаемых:

В этом разбиении последнее слагаемое р₄ равно 2 и не превосходит остальные слагаемые больше, чем на 1. Поэтому в очередном разбиении нужно принять значения всех слагаемых равными 1, а затем увеличить длину разбиения ещё на одно слагаемое р₅. По остаточной формуле его значение должно быть равно 3. Следовательно, очередное разбиение будет иметь вид:

Таким образом на каждом шаге алгоритма либо строится следующее в лексиграфическом порядке разбиение с тем же количеством слагаемых, либо число слагаемых увеличивается на 1 и получается расширенное разбиение, где все слагаемые, кроме последнего равны 1. Рассмотренный процесс генерации разбиений завершается, когда на конечном шаге получится разбиение с максимальным числом слагаемых l=n, где все слагаемые равны 1:

Существенным недостатком алгоритма Гинденбурга, снижающим его эффективность, является необходимость обратного просмотра слагаемых каждого разбиения. Этого недостатка лишён более совершенный в вычислительном отношении алгоритм, предложенный Г. Эрлихом. Этот алгоритм генераций разбиений натурального числа, который использует мультимножественную запись его слагаемых, порождая разбиения в словарном порядке.

В мультимножественных обозначениях учитывается кратность слагаемых разбиения. Это даёт возможность записать разбиение любого натурального числа n на l мультислагаемых в следующем формате:

В этой записи m_i обозначает кратность слагаемого p_i, а слагаемые перечислены в порядке убывания их величин:

Например, один из вариантов разбиения числа 7на 2 мультислагаемых 4 и 3 может быть записан следующим образом:

В этой записи слагаемое р₁=2 входит в разбиение с кратностью m₁=2, а слагаемое р₂=1 учтено в разбиении с кратностью m₂=3. При этом p₁ трого больше p₂.

Мультимножественная запись позволяет построить алгоритм прохождения разбиений, который переходит от текущего разбиения к следущему в словарном порядке, рассматриивая только самый первый элемент разбиения m_lp_l без анализа предыдущих слагаемых как в алгоритме Гринденбурга. Способ конструирования очередного разбиения зависит от кратности m_l последнего слагаемого текущего разбиения. При этом рассматриваются 2 случая:

и

В 1-м случае (m_l>1) можно исключить из разбиения 2p_l, чтобы иметь возможность добавить (ещё) одно слагаемое со значением (p_l+1). Во 2-м случае (m_l=1) за счёт 2-х последних мультислагаемых(m_l-1p_l-1) и (m_lp_l) можно добавить ещё одно слагаемое со значением (p_l-1+1). В любом то, что остаётся от уменьшаемых мультислагаемых превращается в соответствующее число единиц последнего мультислагаемого и формируется очереднок разбиение. Указанный процесс должен начинаться с разбиения (n1), где слагаемые равны 1 и завершаться разбиением (1n) из одного мультислагаемого.

Выполнение шагов алгоритма Эрлиха иллюстрирует следующий пример генерации разбиений натурального числа 7:

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