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

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

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

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.