Композицией называется представление любого натурального числа в форме упорядоченной суммы целых положительных (или неотрицательных) слагаемых. По сравнению с разбиениями целых чисел, для композиций важен порядок записи слагаемых. Поэтому композиции можно рассматривать как упорядоченные разбиения целых чисел, которые образуются различными перестановками (с возможным повторением) своих слагаемых. Например, в следующей таблице перечислены различные композиции для всех возможных разбиений числа 7 на 3 части:
Таблица 1    
разбиение числа 7копозиции числа 7
5125+1+1; 1+5+1; 1+1+5.
4214+2+1; 4+1+2; 2+4+1; 2+1+4; 1+4+2; 1+2+4.
3213+3+1; 3+1+3; 1+3+3.
3223+2+2; 2+3+2; 2+2+3.

В общем случае для подсчета или перечисления композиций любого натурального числа n его удобно представить в единичной (палочной) системе счисления, записав подряд n единиц. При этом в (n−1) промежутках между ними можно размещать, например, знаки '|' для разделения слагаемых композиции. Для наглядности в оставшиеся свободные промежутки, где отсутствует разделитель, можно поставить знаки +. Тогда суммы единиц между соседними разделителями, а также по краям такой записи будут определять значения слагаемых композиции. Формально, каждый промежуток можно кодировать двоичной цифрой 1, когда в нем был поставлен знак разделителя, или цифрой 0, если промежуток свободен. Таким образом, каждой композиции любого натурального числа n можно сопоставить бинарный код из (n−1) двоичных разрядов, который отражает способ выбора подмножества промежутков для знаков разделителей в его единичной записи. Пример всех этих представлений для одной из композиций числа 7 показан на следующей диаграмме:
7 = 1 | 1 | 1 + 1 | 1 + 1 | 1 <− единичная запись( 1 1 0 1 0 1 ) <− двоичный код7 = 1+ 1 + 2 + 2 + 1<− композиция
При подсчете и пересчете композиций целесообразно выделить 3 случая, которые отличаются характером ограничений на число слагаемых, когда оно может быть произвольно, фиксировано и ограничено сверху заданным значением. Способы подсчета и перечисления композиций во всех этих случаях рассмотрены ниже.
В наиболее неограниченном случае количество слагаемых композиции не фиксировано. Тогда разнообразие композиций для любого натурального числа n определяет множество всех 2n−1 бинарных векторов из (n−1) двоичных разрядов, которые кодируют все варианты разделения его единичной записи. Их последовательные значения от 0n−1 до 1n−1 можно получить методом двоичного счета и преобразовать в соответствующие композиции. Для этого нужно сначала дополнить его нулевым разрядом слева и вставить один нулевой разряд справа от каждого единичного разряда. После такого расширения бинарного кода необходимо заменить каждый единичный разряд знаком +, а вместо каждой группы стоящих подряд нулевых разрядов нужно записать значение их числа. Рассмотренный способ генерации композиций с произвольным количеством слагаемых иллюстрирует следующая таблица, где перечислены двоичные коды, их расширения, с подчеркнутыми дополнительными нулевыми разрядами, и результирующие композиции числа 3:
Таблица 2    
двоичный код00011011
расширенный код0000010010001010
композиция32+11+21+1+1

Теоретически более интересен случай, когда количество слагаемых композиций целого числа n>1 фиксировано значением m<n. Каждая такая композиция соответствует бинарному вектору из n−1 двоичных разрядов, где ровно m−1 разрядов имеют значение 1. Эти бинарные векторы дают двоичный код искомых композиций, а их общее количество равно числу сочетаний из n−1 двоичных разрядов по m−1 единичных разрядов и определяется по следующей формуле:
C(n−1, m−1) = (n − 1)!(m − 1)! (n − m)!.
Для систематического перечисления композиций с фиксированным числом слагаемых в общем случае можно применять методы генерации бинарных сочетаний, которые интерпретируются как двоичные коды искомых композиций и позволяют определить их слагаемые. Можно также применить алгоритм перечисления сочетаний натуральных чисел, которые должны выбираться из числового диапазона от 1 до (n−1) по (m−1) чисел. Каждый вектор сочетаний, порождаемый этим алгоритмом, нужно дополнить слева и справа значениями 0 и n, соответственно. Тогда разности соседних значений полученного числового набора будут равны слагаемым искомой композиции числа n из m слагаемых. Следующий пример иллюстрирует такое преобразование сочетания натуральных чисел в композицию для случая n=7 и m=5:
(1, 2, 4, 6) −> (0 − 1 − 2 − 4 − 6 − 7) −> (1 + 1 + 2 + 2 + 1 + 1 = 7).
Формально, любые композиции числа n из m натуральных слагаемых соответствуют решениям следующего уравнения, где все переменные могут принимать только целые положительные значения Xi>0, обозначая слагаемые композиции:
X1 + … + Xi + … + Xm = n.
Более общий случай, когда допустимы любые целые неотрицательные значения переменных Xi≥0, соответствует композициям числа n, в которых количество положительных слагаемых не превышает величину m. В такой ситуации некоторые слагаемые могут принимать значение 0, а требуемую сумму n обеспечивают положительные значения остальных слагаемых. Поиск таких неотрицательных решений и композиций основан на переходе к эквивалентному уравнению, где все переменные положительные целые величины, как раньше. Этот переход обеспечивается следующей заменой переменных:
Xi = (Yi − 1); i = 1, …, m.
В результате такой подстановки получается следующее уравнение, где целочисленные значения всех переменных гарантированно положительны Yi>0, а правая часть будет на m больше, чем в исходном уравнении с неотрицательными переменными Xi≥0:
Y1 + … + Yi + … + Ym = n + m.
Ясно, что все его целые положительные решения соответствуют композициям числа (n+m) из m натуральных слагаемых. Количество композиций такого типа определяет число сочетаний из (n+m−1) чисел по (m−1) или по n чисел. Его можно найти по следующей формуле:
C(n+m−1, m−1) =(n+m−1)!(m−1)! n! = C(n+m−1, n).
Для их перечисления можно применить рассмотренный выше алгоритм, учитывая, что значение каждого слагаемого композиции числа n+m нужно уменьшить на 1, чтобы получить слагаемые искомых композиций числа n. Естественно, что при этом некоторые из них становятся равны 0. Такое преобразование отражает взаимно однозначное соответствие переменных и уравнений этих композиций, которое было установлено выше. Его иллюстрирует следующий пример, где перечислены все 4 композиции числа n=3 из m=2 неотрицательных слагаемых, которые были получены по композициям числа n+m=5 из m=2 положительных слагаемых:
5 = Y1 + Y2 :1 + 4 2 + 33 + 24 + 1(Y1 , Y2 > 0)3 = X1 + X2 :0 + 31 + 22 + 13 + 0(X1 , X2 ≥ 0)