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

[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.....

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

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

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

[samec]

а по-моему всё сходится

P(1)=1 - это ведь точно? А получили мы это по вышеприведенной формуле вот как:
P(1), n=1, по формуле: P(1)=P(1-1)=P(0)=1.
P(2), n=2, по формуле: P(2)=P(2-1)+P(2-2)=P(1)+P(0)=P(0)+P(0)=2P(0)=2.
P(3), n=3, P(3)=P(2)+P(1)=2P(0)+P(0)=3P(0)=3.
P(4),n=4, P(4)=P(3)+P(2)=3P(0)+2P(0)=5P(0)=5.
P(5),n=5, P(5)=P(4)+P(3)-P(0) = 5P(0)+3P(0)-P(0) = 7P(0)=7.
P(6),n=6, P(6)= P(5)+P(4)-P(1) = 7P(0)+5P(0)-P(0)=11P(0)=11.
P(7),n=7, P(7)=P(6)+P(5)-P(2)-P(0)=11P(0)+7P(0)-2P(0)-P(0) = 15P(0)=15.
ну и так и далее
p(8) = 22
p(9) = 30
p(10) = 42
p(100) = 190 569 292
p(1000) = 24 061 467 864 032 622 473 692 149 727 991


Сообщение отредактировано: samec - 25.11.2008 13:00

[Гость]

Нет, ноль не входит в разложения. Для убедительности - вот еще разложение для 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.
Можешь сам продолжить проверку на других числах.

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

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

да нет все правилно просто ты сного не учитываешь p(0).
вот настоящее разложние:
p(4)=p(3)+p(2)=(p(2)+p(1))+(p(1)+p(0))=(((p(1)+p(0))+p(1))+(p(1)+p(0))=5*(p(0))=
5
спасибо за все.

[2ral]

Блин забыл войти но это мой пост, сорри

[Lapp]

Хорошо, убедили .
Я для себя нашел тоже способ примириться с этим. На самом деле ноль есть в каждом разложении:
(1,1,1,1,0)
(2,1,1,0)
(2,2,0)
(3,1,0)
(4,0)
И этот ноль - он "неубираемый" . Тогда все встает на свои места

samec, +1