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

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

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

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

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

Примеры

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

${\begin{alignedat}{2}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{alignedat}}$

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

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

Комбинаторное доказательство

Самый длинный способ записать число $n$ — представить его в виде суммы $n$ единиц:

$$n=\underbrace {1+1+\ldots +1} _{n\ {\text{раз}}}$$

Заменим теперь в этой записи все плюсы на пустые квадраты. Всего этих пустых квадратов $n-1$, на единицу меньше, чем количество единиц:

$$n=1\ \Box \ 1\ \Box \ldots \Box \ 1\ \Box \ 1$$

В каждый из этих квадратов можно писать либо ($+$), либо запятую ($,$). Каждое заполнение всех квадратов даст в результате очередное разложение числа. Получается, что каждое разложение числа $n$ на слагаемые можно представить как размещение с повторением из двух символов (плюса и запятой) по $n-1$ квадратам:

$${\overline {A}}_{2}^{n-1}=2^{n-1}$$ ■

Доказательство через теорию множеств

Для доказательства этого утверждения достаточно построить биекцию между композициями 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)$-элементного множества, то есть биномиальному коэффициенту ${\tbinom {n-1}{k-1}}$.■

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

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

Литература

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