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

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

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

При фиксированной длине композиций в них иногда допускают слагаемые, равные 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 с возможными нулевыми частями совершенно любой длины, то количество композиций, вообще говоря, будет бесконечным.