Количество способов разложить число в сумму (композиции)

[Mike Krasnov]

Задача следующая:
Найти количество возможных вариантов разложения натурального числа в сумму натуральных чисел. Дополнительное условие: два одинаковых ряда с разным порядком слагаемых в них считать различными.
Заранее благодарен.

[maxal]

Такие разложения называются композициями. Для числа $n$ количество композиций с $k$ частями (слагаемыми) равно ${n-1\choose k-1}.$ Общее количество композиций равно

$$\sum_{k=1}^n {n-1\choose k-1} = 2^{n-1}.$$

[hclubmk]

Я извиняюсь за поднятие старой темы, но вопрос касается именно этой задачи.
Каково будет решение (число композиций) при условии, что слагаемые могут принадлежать диапазону, предположим от 1 до m (где m<n)?
Спасибо.

[maxal]

hclubmk в сообщении #376563 писал(а):

Каково будет решение (число композиций) при условии, что слагаемые могут принадлежать диапазону, предположим от 1 до m (где m<n)?

Производящая функция равна ($k$ индексирует количество частей в композиции):

$$\sum_{k=0}^{\infty} (x+x^2+\dots+x^m)^k = \frac{1}{1-(x+x^2+\dots+x^m)} = \frac{1-x}{1-2x+x^{m+1}}.$$

Коэффициент при $x^n$ равен:

$$[x^n] \frac{1-x}{2-2x+x^{m+1}} = [x^n] \frac{1}{1-2x+x^{m+1}} - [x^{n-1}]\frac{1}{1-2x+x^{m+1}}.$$

Ну и остается заметить, что

$$[x^t] \frac{1}{1-2x+x^{m+1}} = [x^t] \sum_{j=0}^{\infty} (2x-x^{m+1})^j = \sum_{i=0}^{\lfloor t/(m+1)\rfloor} \binom{t-mi}{i} (-1)^i 2^{t-(m+1)i}.$$

[hclubmk]

maxal
Спасибо за ответ. Для меня такие выкладки достаточно сложны. Я прекрасно понимаю, что Вы можете меня послать курить матчасть, но если существует такая возможность, объясните "на пальцах" (на примере), как практически применить Ваши формулы.

[maxal]

hclubmk в сообщении #376694 писал(а):

Я прекрасно понимаю, что Вы можете меня послать курить матчасть, но если существует такая возможность, объясните "на пальцах" (на примере), как практически применить Ваши формулы.

Ну, например, на PARI/GP указанные формулы можно реализовать так:

? aux(t,m) = sum(i=0,t\(m+1), binomial(t-m*i,i) * (-1)^i * 2^(t-(m+1)*i) )
%1 = (t,m)->sum(i=0,t\(m+1),binomial(t-m*i,i)*(-1)^i*2^(t-(m+1)*i))

? ncomp(n,m) = aux(n,m) - aux(n-1,m)
%2 = (n,m)->aux(n,m)-aux(n-1,m)

? matrix(10,10,n,m,ncomp(n,m))
%3 = 
[1 1 1 1 1 1 1 1 1 1]
[1 2 2 2 2 2 2 2 2 2]
[1 3 4 4 4 4 4 4 4 4]
[1 5 7 8 8 8 8 8 8 8]
[1 8 13 15 16 16 16 16 16 16]
[1 13 24 29 31 32 32 32 32 32]
[1 21 44 56 61 63 64 64 64 64]
[1 34 81 108 120 125 127 128 128 128]
[1 55 149 208 236 248 253 255 256 256]
[1 89 274 401 464 492 504 509 511 512]

Как видим, полученные значения для $n,m=1,2,\dots,10$ сходятся с приведёнными в последовательности A126198. Значит, я нигде не наглюкал.

[hclubmk]

Жесть. Кроме матчасти - курить семантику PARI/GP.
Нет ли возможности всё-же разъяснить назначение операторов, поскольку есть необходимость реализовывать на другом языке программирования (скажем "С").

[maxal]

hclubmk в сообщении #376924 писал(а):

Нет ли возможности всё-же разъяснить назначение операторов, поскольку есть необходимость реализовывать на другом языке программирования (скажем "С").

Может, мне ещё за вас программу написать?! Вам нужно - вы и разбирайтесь. Вся необходимая информация приведена выше.

[hclubmk]

maxal
Я не специалист в таких узких областях, поэтому и попросил разъяснений, а не готовое решение (наверно есть разница?).
Впрочем, Вы и так достаточно много внимания уделили моей новоявленной на форуме персоне.
В любом случае, спасибо.

[scwec]

Хотел бы обратить внимание модераторов и других активных участников на их большую готовность отвечать на совершенно бессмысленные вопросы мало касающиеся математики и неготовность отвечать на принципиальные вопросы. Не хочу делать глубокомысленных выводов, однако их пора, видимо, пришла. Успехов Вам.

Предупреждение за оффтопик!

-- Сб дек 04, 2010 22:33:11 --

Приношу глубокие извинения за, может быть, обидные слова. Такие у Вас, выходит, правила.
Онако, ведь "За Державу обидно". Ну что же, как есть, так пусть и будет.
С уважением Швецов.

[tess]

Раньше количество вариантов считали так: выложим все единицы числа $n$ в ряд, имеем $n-1$ промежутков. В каждый промежуток можно ничего не вставлять или вставлять +. Поэтому ответ $2^{n-1}$.
Есть ли решение для числа вариантов, если считать варианты, отличающиеся порядком слагаемых в сумме, за один вариант?

[maxal]

tess в сообщении #469265 писал(а):

Есть ли решение для числа вариантов, если считать варианты, отличающиеся порядком слагаемых в сумме, за один вариант?

Такие "варианты" называются разбиениями - см., например, в википедии.

[SaDiSt007]

ну да уж...

Предупреждение за бессмысленные сообщения и оффтопик!