Композиция числа

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

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

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

ПримерыПравить

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

 

Количество композицийПравить

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

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

См. такжеПравить

ЛитератураПравить

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