Разбиением натурального числа n называется его представление в виде произвольной суммы целых положительных слагаемых (частей) pi > 0:
n = p1 + … + pi + … + pm.
Например, один из вариантов разбиения числа n=7 на m=4 слагаемых дает следующая сумма:
7 = 3 + 2 + 1 + 1.
Порядок перечисления слагаемых в разбиении значения не имеет. Поэтому следующие два разбиения, числа 7 на 3 слагаемых считаются эквивалентными комбинаторными объектами:
7 = 1 + 4 + 2 = 2 + 1 + 4.
Однако, исходя из алгоритмических соображений, более удобно располагать части разбиений в таком порядке, когда их величины не убывают или не возрастают:
p1 ≤ … ≤ pi < … ≤ pm или p1 ≥ … ≥ pi ≥ … ≥ pm .
Когда это нужно, для сокращения записи разбиений опускают знак + и обозначают показателем степени сумму равных частей. Например, следующие две записи специфицируют одинаковое разбиение числа 7: где величины слагаемых не возрастают:
7 = 3 + 2 + 1 + 1 = 3212.
Для наглядности разбиение любого числа можно представить фигурой из рядов точек, которая называется точечным графом Ферре. В этом графе каждая часть разбиения изображается рядом точек, число которых равно ее значению. Такие ряды из точек располагаются один под другим и выровнены по левой границе, а число точек в каждом следующем ряду не больше, чем в предыдущем, так как считается, что все части разбиения перечислены в таком порядке, когда их величины не возрастают. Транспонирование графа Ферре для любого разбиения, когда ряды и колонки его точек меняются местами, дает сопряженное разбиение того же числа. Например, графы Ферре двух сопряженных разбиение числа 7 показаны на следующей диаграмме:
Графы Ферре обеспечивают геометрическую наглядность разбиений чисел и используются для обоснования их свойств. Однако основные практические проблемы вычислительной обработки разбиений чисел связаны с решением задач подсчета их общего количества и систематического перечисления. В общем случае суммарное количество разбиений p(n) для любого заданного натурального числа n можно определить по следующему рекуррентному соотношению:
p(n) = p(n — 1) + p(n — 2) — p(n — 5) — p(n — 7) + ... + (-1)k-1p(n — 3k2-k2) + (-1)k-1p(n — 3k2+k2) + ...
В этом соотношении предполагается, что все аргументы слагаемых правой части должны быть неотрицательны и считается, что p(0)=1. Кроме того, для его практической обработки полезно заметить, что разности аргументов соседних однозначных слагаемых в правой части образуют ряд натуральных чисел, а разности аргументов разнозначных соседних пар слагаемых являются последовательными нечетными числами, начиная с 3. В следующем примере демонстрируется последовательность вычисления числа разбиений p(n) для всех значений n от 1 до 7:
Для справки все возможные разбиения целых чисел n от 1 до 7 на различное количество частей m перечислены в следующей таблице:
Рис. 1.  
Алгоритмически более сложной проблемой является систематическое перечисление различных разбиений для любого заданного числа n. Если нет ограничений по количеству, величине или числу повторений частей разбиений, то для решения этой задачи могут применяться алгоритмы, предложенные Гинденбургом и Эрлихом, которые рассмотрены ниже.
Алгоритм Гинденбурга порождает разбиения любых натуральных чисел в порядке увеличения количества слагаемых, а разбиения равной длины перечисляются в лексиграфическом порядке.
В общем случае шаги алгоритма Гинденбурга начинаются с разбиения, которое состоит только из одного слагаемого, равного n (p1=n). У последующих разбиений число слагаемых m не убывает, а сами слагаемые записываются в неубывающем порядке своих величин. При этом каждое очередное разбиение на m слагаемых строится по текущему разбиению следующим образом. Нужно просмотреть текущее разбиение справа налево, с целью найти наибольшее слагаемое pi, которое отличается от последнего слагаемого pm не меньше, чем на 2:
pm − pi ≥ 2.
Слагаемое pi нужно увеличить на 1 и присвоить его новое значение всем слагаемым pj, справа от него до предпоследнего слагаемого, включительно. Указанное преобразование текущего разбиения можно формально записать следующим образом:
pj = pi + 1 для всех j = i, …, (m − 1).
С учетом полученных значений последнее слагаемое pm вычисляется по следующей остаточной формуле:
pm = n − (p1 + … + pj + … + pm−1).
В следующем примере приведены все последовательные разбиения числа 7 на 4 слагаемых, которые получены таким способом, а образующее слагаемое 1 выделено подчеркиванием:
1 + 1 + 1 + 4 −> 1 + 1 + 2 + 3 −> 1 + 2 + 2 + 2 .
В общем случае каждая серия из последовательных разбиений на m слагаемых завершается лексиграфически наибольшим разбиением, где последнее слагаемое pm не превосходит по величине остальные слагаемые больше, чем на 1. Так как слагаемые разбиений записываются в неубывающем порядке своих величин, то такое соотношение их значений отражает следующее неравенство:
pm − p1 ≤ 1.
В этом случае нужно перейти к построению следующей серии лексиграфически упорядоченных разбиений на (m+1) слагаемых, где им присваиваются следующие начальные значения:
p1 = 1, …, pm = 1, pm+1 = (n − m).
Указанный переход показан в следующем примере для последовательных разбиений числа 7 на 4 и 5 слагаемых:
1 + 2 + 2 + 2 −> 1 + 1 + 1 + 1 + 3.
Таким образом, на каждом шаге алгоритма Гинденбурга либо по текущему разбиению строится следующее в лексиграфическом порядке разбиение с тем же количеством слагаемых, либо их число увеличивается на 1 и формируется опорное разбиение, где значения всех слагаемых, кроме последнего, равны 1. Этот процесс генерации разбиений должен быть завершен, когда на конечном шаге получится разбиение с максимальным числом частей, где все значения равны 1:
n = (p1 = 1) + … + (pi = 1) + … + (pn = 1).
Можно заметить, что для любого целого числа n последовательность разбиений, формируемых алгоритмом Гинденбурга, частично упорядочена по количеству слагаемых от 1 до n. Поэтому разбиения равной длины всегда оказываются рядом. Это можно использовать для перечисления всех разбиений любого целого числа n, где количество слагаемых фиксировано или ограничено заданным значением m<n. Интересно, что величины наибольших слагаемых их сопряженных разбиений оказываются равны или ограничены значением m. Это предоставляет возможность перечислять разбиения, где величина слагаемых ограничена заданным значением.
Не менее гибкий, но гораздо более совершенный в вычислительном отношении алгоритм Эрлиха порождает все разбиения любого заданного числа в словарном порядке, используя мультимножественную запись слагаемых, где учитывается их кратность. Это дает возможность записать разбиение любого числа n на m≤n мультислагаемых в следующем формате:
n = k1p1+ … + kipi + … + kmpm .
В этой записи ki обозначает кратность слагаемого pi, а все слагаемые перечислены в порядке убывания их величин:
p1 > … > pi > … > pm .
Например, разбиение числа 7 на 2 мультислагаемых 2 и 1 с кратностями 2 и 3, соответственно, выглядит так:
7 = 2∙2 + 3∙1 = (2 + 2) + (1 + 1 + 1).
Мультимножественная запись слагаемых позволяет построить алгоритм генерации разбиений целых чисел, который переходит от текущего разбиения к следующему в словарном порядке, рассматривая только самое правое мультислагаемое без анализа предыдущих частей разбиения как было в алгоритме Гинденбурга. Способ конструирования очередного разбиения зависит от кратности последнего мультислагаемого текущего разбиения. При этом требуется рассмотреть следующие два случая:
km > 1 и km = 1.
В первом случае нужно исключить из разбиения значение (2∙pm), чтобы получить возможность добавить (еще) одно мультислагаемое со значением (pm+1). Во втором случае нужно добавить еще одно мультислагаемое со значением (pm−1+1), исключив два последних мультислагаемых. В любом случае, то, что остается от уменьшаемых мультислагаемых должно быть превращено в соответствующее число единиц для последнего мультислагаемого следующего разбиения. Этот процесс должен начинать с разбиения, где все части равны единице, и завершаться разбиением из одного мультислагаемого. Выполнение шагов алгоритма Эрлиха иллюстрирует следующая таблица, где показана генерация разбиений числа 7:
Таблица 1    
мультиразбиениеисключитьдобавитьостаток
71 = 1+1+1+1+1+1+1211251
12 + 51 = 2+(1+1+1+1+1)211231
22 31 = (2+2)+(1+1+1)211211
32 + 11 = (2+2+2)+132, 111341
13 + 41 = 3+(1+1+1+1)211221
13 + 12 + 21 = 3+2+(1+1)21120
13 + 22 = 3+(2+2)221311
23 + 11 = (3+3)+122, 111431
14 + 31 = 4+(1+1+1)211211
14 + 12 + 11 = 4+2+112, 11130
14 + 13 = 4 + 314, 131521
15 + 21 = 5+(1+1)21120
15 + 12 = 5+215, 121611
16 + 11 = 6+116, 11170
17 = 7---