IPB
ЛогинПароль:

 
 Ответить  Открыть новую тему 
> количество разбиений
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 22
Пол: Мужской
Реальное имя: Neymanov Tural

Репутация: -  0  +


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

заранее спс.


--------------------
Смейся и весь мир будет смеяться вместе с тобой, плачь и ты будешь плакать в одиночестве (Old Boy)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской
Реальное имя: Юра

Репутация: -  1  +


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


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(samec @ 24.11.2008 1:36) *
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, ..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

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

Ммм?..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 22
Пол: Мужской
Реальное имя: Neymanov Tural

Репутация: -  0  +


Цитата(Lapp @ 24.11.2008 7:18) *

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

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

Ммм?..

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

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

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


--------------------
Смейся и весь мир будет смеяться вместе с тобой, плачь и ты будешь плакать в одиночестве (Old Boy)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(2ral @ 24.11.2008 23:41) *
а мне кажется верно - просто 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.
Можешь сам продолжить проверку на других числах.

Цитата(2ral @ 24.11.2008 23:41) *
я токо одно не понял - откуда берутся 1 2 5 7 12.....
Ну я же написал формулу..

Цитата(2ral @ 24.11.2008 23:41) *
а так спасибо.
Да пока не за что..


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Бывалый
***

Группа: Пользователи
Сообщений: 180
Пол: Мужской
Реальное имя: Юра

Репутация: -  1  +


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

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.
ну и так и далее smile.gif
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
smile.gif

Сообщение отредактировано: samec -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






Цитата(Lapp @ 25.11.2008 0:57) *

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

 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 22
Пол: Мужской
Реальное имя: Neymanov Tural

Репутация: -  0  +


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


--------------------
Смейся и весь мир будет смеяться вместе с тобой, плачь и ты будешь плакать в одиночестве (Old Boy)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


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

samec, +1


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 16:50
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name