Композиция числа - NiNa.Az

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

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

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

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

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

Примеры

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

$${\displaystyle n=1\ \Box \ 1\ \Box \ldots \Box \ 1\ \Box \ 1}$$

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

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

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

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

${\displaystyle n_{1}=m_{1}}$, ${\displaystyle n_{i}=m_{i}-m_{i-1}}$ при ${\displaystyle i=2,\;\ldots ,\;k-1}$ и, наконец, ${\displaystyle n_{k}=n-m_{k-1}}$.

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

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

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

Литература

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