Композиция (теория чисел)

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

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

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

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

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

Примеры

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

• 5 = 5;
• 5 = 4 + 1;
• 5 = 3 + 2;
• 5 = 3 + 1 + 1;
• 5 = 2 + 3;
• 5 = 2 + 2 + 1;
• 5 = 2 + 1 + 2;
• 5 = 2 + 1 + 1 + 1;
• 5 = 1 + 4;
• 5 = 1 + 3 + 1;
• 5 = 1 + 2 + 2;
• 5 = 1 + 2 + 1 + 1;
• 5 = 1 + 1 + 3;
• 5 = 1 + 1 + 2 + 1;
• 5 = 1 + 1 + 1 + 2;
• 5 = 1 + 1 + 1 + 1 + 1.

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

В общем случае существует 2^{n − 1} композиций числа n и $\binom{n-1}{k-1}$ композиций числа n длины k. Для доказательства этого утверждения достаточно построить биекцию между композициями 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₁ = m₁, n_i = m_i − m_{i − 1} при $i=2,\;\ldots,\;k-1$ и, наконец, n_k = n − m_{k − 1}.

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

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

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

См. также

• Разбиение

Литература

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