Просмотр исходного текста страницы Нахождение количества разбиений числа на слагаемые

Задача: Дано число n, найти [http://oeis.org/A000041 количество его различных разбиений на слагаемые] <tex> m_0 + m_1 + m_2 \dots + m_k = n </tex> так что <tex> \forall i: m_i \le m_{i+1} </tex>.

__TOC__

== Алгоритм за n sqrt(n) ==
Рассмотрим самый быстрый алгоритм их нахождения - за <tex> O(n \sqrt{n}) </tex>. Если кто хочет добавить другие алгоритмы, добавьте.

Итак, обозначим количество таких разбиений за <tex> p(n) </tex>.

Рассмотрим бесконечное произведение
<tex> (1 + x + x^2 + \dots)(1 + x^2 + x^4 + \dots) \dots (1 + x^k + x^{2k} + \dots) \dots </tex>
Каждый член произведения получается в результате умножения мономов(одночленов), взятых по одному из каждой скобки. Если в первой скобке взять <tex>x^{m_1}</tex>, во второй — <tex>x^{2m_2}</tex> и т.д., то их произведение будет равно <tex>x^{m_1 + 2m_2 + 3m_3 + \dots}.</tex> Значит, после раскрытия скобок получится сумма мономов вида <tex>x^{m_1 + 2m_2 + 3m_3 + \dots}</tex>.

Можно увидеть, что <tex> x^n </tex> встретится в полученной бесконечной сумме столько раз, сколькими способами можно представить <math>n</math> как сумму <tex>m_1 + 2m_2 + 3m_3 + ...</tex> Каждому такому представлению отвечает разбиение числа <tex>n</tex> на <tex>m_1</tex> единиц, <tex>m_2</tex> двоек и т.д. Так получаются все разбиения, так как каждое из них, конечно, состоит из нескольких единиц, нескольких двоек и т.д. Поэтому коэффициент при <tex>x^n</tex> равен числу разбиений <tex>p(n)</tex>.

Посмотрим теперь на выражения в скобках. Каждое из них — бесконечная геометрическая прогрессия. По формуле ее суммирования:
: <tex>1 + x + x^2 + x^3 + ... = \frac{1}{1 - x}</tex>,
: <tex>1 + x^2 + x^4 + x^6 + ... = \frac{1}{1-x^2}</tex>
и т.д. Теперь наш результат можно записать так:
: <tex>p(0) + p(1) x + p(2) x^2 + p(3) x^3 + \dots = \frac{1}{(1-x)(1-x^2)(1-x^3)\dots}</tex>(1)

Рассмотрим произведение <tex>(1-x)(1-x^2)(1-x^3)...</tex>, т.е. знаменатель правой части формулы (1). Раскрывая в нём скобки, получим такой результат:
: <tex>(1 - x)(1 - x^2)(1 - x^3) ... = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - x^{35} - x^{40} + ...</tex>
Показатели в правой части — пятиугольные числа''(при чем тут пятиугольники? o_O )'', т.е. числа вида <tex>(3q^2 \pm q)/2</tex>, а знаки при соответствующих мономах равны <tex>(-1)^q</tex>. Исходя из этого наблюдения, Эйлер предположил, что должна быть верна:

{{Теорема
| about =
Пентагональная теорема Эйлера
| statement = 
<tex> \prod\limits_{k=1}^\infty \left(1-x^k \right) = \sum\limits_{q=-\infty}^\infty (-1)^q x^{(3q^2+q)/2}</tex>
| proof =
Пентагональная теорема оказалась «крепким орешком» — Эйлер сумел доказать её лишь 14 лет спустя.
{{TODO| t = скурить доказательство}}
}}

Умножим обе части равенства (1) на <tex>\prod\limits_{k=1}^\infty \left(1-x^k \right) </tex> и воспользуемся пентагональной теоремой:
: <tex> ( p(0) + p(1) x + p(2) x^2 + \dots)(1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + \dots) = 1 </tex>(2)

Начнем раскрывать скобки, для наглядности мономы с одинаковыми степенями x пишем друг под другом:
: <tex> p(0) + p(1)x + p(2) x^2 + p(3) x^3 + p(4) x^4 + p(5) x^5 + p(6) x^6 + \dots </tex>
::: <tex> - p(0)x - p(1) x^2 - p(2) x^3 - p(3) x^4 - p(4) x^5 - p(5) x^6 - \dots </tex>
::::: <tex>  - p(0) x^2 - p(1) x^3 - p(2) x^4 - p(3) x^5 - p(4) x^6 - \dots </tex>
::::::::::::: <tex>+ p(0) x^5 + p(1) x^6 + \dots </tex>     
// тут ужасное быдлоформатирование, не знаю как нормально расположить друг под другом

Так как p(0) = 1, то оно сокращается с единицей справа. Так что чтобы выражение (2) было удовлетворено при любом x, все коэффициенты должны быть равны 0(вроде так). Поэтому:
: <tex> p(1) = p(0) </tex>
: <tex> p(2) = p(1) + p(0) </tex>
: <tex> p(3) = p(2) + p(1) </tex>
: <tex> p(4) = p(3) + p(2) </tex>
: <tex> p(5) = p(4) + p(3) - p(0) </tex>
и т.д.

Получаем формулу Эйлера, позволяющую последовательно находить числа <tex>p(n)</tex>:
: <tex> p(n) = p(n-1) + p(n-2)+ ... + (-1)^{q+1} (p(n - \frac{3q^2 - q}{2}) + p(n - \frac{3q^2 + q}{2})) </tex>.

Ну и объяснение асимптотики <tex> O(n \sqrt{n}) </tex> - так как <tex> n - \frac{3q^2 + q}{2} \ge 0 </tex> , получаем <tex> q </tex> порядка <tex> \sqrt{n} </tex>, а так как находим n-е число, то получаем <tex> O(n \sqrt{n}) </tex>.

== Используемые материалы ==
* [http://en.wikipedia.org/wiki/Pentagonal_number_theorem Pentagonal number theorem]
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* [http://oeis.org/A000041 Последовательность на OEIS]