Композиция (теория чисел) | это... Что такое Композиция (теория чисел)? (original) (raw)

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

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

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

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

Примеры

Существует 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_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)-элементного множества, то есть биномиальному коэффициенту $\binom{n-1}{k-1}$ .

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

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

См. также

Разбиение

Литература

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