WikiSort.ru - Не сортированное

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

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

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

Примеры

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

• ${\displaystyle 5=5;}$
• ${\displaystyle 5=4+1;}$
• ${\displaystyle 5=3+2;}$
• ${\displaystyle 5=3+1+1;}$
• ${\displaystyle 5=2+3;}$
• ${\displaystyle 5=2+2+1;}$
• ${\displaystyle 5=2+1+2;}$
• ${\displaystyle 5=2+1+1+1;}$
• ${\displaystyle 5=1+4;}$
• ${\displaystyle 5=1+3+1;}$
• ${\displaystyle 5=1+2+2;}$
• ${\displaystyle 5=1+2+1+1;}$
• ${\displaystyle 5=1+1+3;}$
• ${\displaystyle 5=1+1+2+1;}$
• ${\displaystyle 5=1+1+1+2;}$
• ${\displaystyle 5=1+1+1+1+1.}$

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

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

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

См. также

• Разбиение числа

Литература

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

Это заготовка статьи по математике. Вы можете помочь проекту, дополнив её.