количество разбиений Опции

[2ral]

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

заранее спс.

[samec]

(пентагональная теорема Эйлера) Количество p(N) всевозможных разбиений числа N удовлетворяет тождеству
p(N)=p(N-1)+p(N-2)-p(N-5)-p(N-7)+p(N-12)+p(N-15)-...

[Lapp]

p(N)=p(N-1)+p(N-2)-p(N-5)-p(N-7)+p(N-12)+p(N-15)-...

Если эта формула верна (я не могу сейчас подтвердить, не помню), то нелишне привести способ вычисления вычитаемых в скобках - он совершенно неочевиден. Вот он:

Di = (3*i^2 + i)/ 2 , где i = 0, -1, 1, -2, 2, -3, 3, ..

[Lapp]

Что-то не вяжется с этой формулой.. Произведем разложение числа 2:

Реально: (1,1), (2) - то есть 2 разложения.
По этой формуле: P(2) = P(1) (остальные слагаемые имют аргумент >=0), а P(1)=1
Явное расхождение.

Ммм?..

[2ral]

Что-то не вяжется с этой формулой.. Произведем разложение числа 2:

Реально: (1,1), (2) - то есть 2 разложения.
По этой формуле: P(2) = P(1) (остальные слагаемые имют аргумент >=0), а P(1)=1
Явное расхождение.

Ммм?..

а мне кажется верно - просто P(0)=1 так как имеется одно разложение.

я токо одно не понял - откуда берутся 1 2 5 7 12.....
а так спасибо.
жду ответа.

Сообщение отредактировано: 2ral - 25.11.2008 3:42

[Lapp]

а мне кажется верно - просто P(0)=1 так как имеется одно разложение.

Нет, ноль не входит в разложения. Для убедительности - вот еще разложение для 4.

по формуле: p(4) = p(3)+p(2) = (p(2)+p(1)) + p(1) = p(2)+2p(1) = p(1)+2p(1) = 3
реально:
(1,1,1,1)
(2,1,1)
(2,2)
(3,1)
(4)
- всего 5. Если добавишь еще и нули, получишь дополнительно:
(1,1,1,1,0)
(2,1,1,0)
(2,2,0)
(3,1,0)
(4,0)
- еще 5, всего 10.
Можешь сам продолжить проверку на других числах.

я токо одно не понял - откуда берутся 1 2 5 7 12.....

Ну я же написал формулу..

а так спасибо.

Да пока не за что..