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

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

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

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

Примеры

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

$\begin{array}{cc}5& =5=\\ & =4+1=\\ & =3+2=\\ & =3+1+1=\\ & =2+3=\\ & =2+2+1=\\ & =2+1+2=\\ & =2+1+1+1=\\ & =1+4=\\ & =1+3+1=\\ & =1+2+2=\\ & =1+2+1+1=\\ & =1+1+3=\\ & =1+1+2+1=\\ & =1+1+1+2=\\ & =1+1+1+1+1.\end{array}$

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

В общем случае существует $2^{n-1}$ композиций числа n, из которых в точности $(\genfrac{}{}{0ex}{}{n-1}{k-1})$ имеют длину k, где $(\genfrac{}{}{0ex}{}{n-1}{k-1})$ — биномиальный коэффициент, или число сочетаний.

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

Если в композициях числа n длины k разрешить нулевые части, то количество таких композиций будет равно $(\genfrac{}{}{0ex}{}{n+k-1}{k-1})$, поскольку прибавление 1 к каждой части даёт композицию числа Шаблон:Nums уже без нулевых частей. Если рассматривать композиций числа n с возможными нулевыми частями совершенно любой длины, то количество композиций, вообще говоря, будет бесконечным.

Литература

• Шаблон:Книга