Композиция числа

У этого термина существуют и другие значения, см. Композиция.

Не следует путать с Композиция функций.

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

В отличие от композиции, разбиение числа не учитывает порядок следования частей. Поэтому число разбиений числа никогда не превосходит числа композиций.

При фиксированной длине композиций в них иногда также допускают нулевые части.

Примеры

Существует 16 композиций числа 5:

• $5=5;$
• $5=4+1;$
• $5=3+2;$
• $5=3+1+1;$
• $5=2+3;$
• $5=2+2+1;$
• $5=2+1+2;$
• $5=2+1+1+1;$
• $5=1+4;$
• $5=1+3+1;$
• $5=1+2+2;$
• $5=1+2+1+1;$
• $5=1+1+3;$
• $5=1+1+2+1;$
• $5=1+1+1+2;$
• $5=1+1+1+1+1.$

Количество композиций

В общем случае существует $2^{n-1}$ композиций числа n, из которых в точности $\textstyle \binom{n-1}{k-1}$ имеют длину k. Для доказательства этого утверждения достаточно построить биекцию между композициями n длины k и $(k-1)$-элементными подмножествами $(n-1)$-элементного множества. Поставим в соответствие композиции $n=n_1+\ldots+n_k$ подмножество множества $\{1,\;\ldots,\;n-1\}$, состоящее из частичных сумм: $\{n_1,\;n_1+n_2,\;\ldots,\;n_1+\ldots+n_{k-1}\}$. Очевидно, у этого соответствия есть обратное: по подмножеству $\{m_1,\;\ldots,\;m_{k-1}\}$, элементы которого упорядочены по возрастанию, можно восстановить исходную композицию:

$n_1=m_1$, $n_i=m_i-m_{i-1}$ при $i=2,\;\ldots,\;k-1$ и, наконец, $n_k=n-m_{k-1}$.

Таким образом, построенное отображение биективно, и поэтому количество композиций числа n длины k равно количеству $(k-1)$-элементных подмножеств $(n-1)$-элементного множества, то есть биномиальному коэффициенту $\textstyle\binom{n-1}{k-1}$. Для подсчета общего числа композиций числа n достаточно или просуммировать эти биномиальные коэффициенты, или использовать то же отображение для построения биекции между всеми композициями числа n и всеми подмножествами $(n-1)$-элементного множества.

Если в композициях числа n длины k разрешить нулевые части, то количество таких композиций будет равно $\textstyle\binom{n+k-1}{k-1}$, поскольку прибавление 1 к каждой части даёт композицию числа n + k уже без нулевых частей. Вопрос об общем количестве композиций числа n с возможными нулевыми частями лишён смысла, так как оно бесконечно.

См. также

• Разбиение числа

Литература

• Сачков В. Н. Комбинаторные методы дискретной математики. — М.: Наука, 1977. — С. 241. — 319 с.