1679
правок
Изменения
м
Новая страница: «Задача: Дано число n, найти [http://oeis.org/A000041 количество его различных разбиений на слагаемые] <…»
Задача: Дано число 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_{n=-\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]
__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_{n=-\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]
