Русская Википедия:Композиция числа

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

Примеры

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

<math>\begin{alignat}{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{alignat}</math>

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

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

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

Литература

• Шаблон:Книга