Изменения
→Алгоритм за O(N3): так даже лучше
{{Задача: Дано число |definition = По заданному числу <tex>n, </tex> найти [http://oeis.org/A000041 количество его различных разбиений на положительные слагаемые] <ref name="amount" /> <tex> m_0 + m_1 + m_2 + \dots ldots + m_k = n </tex> так , что при всех <tex> i\forall i: colon m_i \le leqslant m_{i+1} </tex>.}}
__TOC__
== Алгоритм за O(N<sup>3</sup>)==Пусть <tex>P(n, m, k)</tex> — количество разбиений числа <tex>n</tex> на <tex>m</tex> слагаемых, каждое из которых не превосходит <tex>k</tex>.Имеет место следующее рекуррентное соотношение:<p><tex dpi = "145">P(n sqrt, m, k) = \left \{\begin{array}{ll}P(n, m, k - 1) + P(n - k, m - 1, k), & 0 < m \leqslant n, 0 < k \leqslant n \\P(n, m, n), & k > n \\1, & n = 0, m = 0 \\0, & \text{otherwise} \end{array} \right. </tex></p> Рассмотрим множество разбиений числа <tex>n</tex> на <tex>m</tex> слагаемых, каждое из которых не больше <tex>k</tex>. Разделим его на две непересекающиеся группы — в первой будут всеразбиения, которые не содержат в качестве старшего слагаемого <tex>k</tex>. Таких разбиений <tex>P(n, m, k - 1)</tex>. Во второй — все разбиения со старшим слагаемым <tex>k</tex>. Их столько же, сколько разбиений числа <tex>n - k</tex> на <tex>m - 1</tex> слагаемое, каждое из которых не больше <tex>k</tex>, то есть <tex>P(n - k, m - 1, k)</tex>. Количество всех разбиений числа равно <tex>\sum\limits_{i=0}^nP(n, i, n)</tex>. Реализация данного алгоритма методом [[Динамическое программирование|динамического программирования]] с меморизацией будет иметь асимптотику <tex>O(n^{3})</tex>. == Алгоритм за O(N<sup>2</sup>) ==Обозначим <tex>P(n,k)</tex> — количество разбиений числа <tex>n</tex> на слагаемые, каждое из которых не превосходит <tex>k</tex>. Оно удовлетворяет следующей рекурентной формуле:<p><tex dpi="145">P(n,k) = \left \{ \begin{array}{ll} P(n,k - 1) + P(n - k, k), & 0 < k \leqslant n \\ P(n, n), & k > n \\1, & n = 0, k = 0 \\0, & n \neq 0 , k = 0 \end{array} \right.</tex></p> Заметим, что нам не нужно считать количество слагаемых <tex>m</tex> в разбиении. Достаточно посчитать <tex>P(n, k)</tex> — количество разбиений числа <tex>n</tex> на произвольное количество слагаемых, каждое из которых не больше <tex>k</tex>. Рассмотрим множество таких разбиений. Разделим его на две непересекающиеся группы. В первую войдут те разбиения, в которых отсутствует слагаемое <tex>k</tex>. Очевидно, таких разбиений <tex>P(n, k - 1)</tex>. Во второй группе — те разбиения, в которые слагаемое <tex>k</tex> вошло. Их количество совпадает с количеством разбиений числа <tex>n - k</tex> на слагаемые, каждое из которых не превосходит <tex>k</tex>, и равно <tex>P(n - k, k)</tex>. Количество всех разбиений числа <tex>n</tex> равно <tex>P(n,n)</tex>. Асимптотика <tex>O(n^{2})</tex>. == Алгоритм за O(N<sup>3/2</sup>) ==Рассмотрим самый быстрый алгоритм их нахождения - количества разбиений числа <tex>n</tex> на слагаемые, который работает за <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>0 \leqslant x < 1</tex>, по формуле ее суммирования:: <tex dpi = "145">1 + x + x^2 + x^3 + \dots = \frac{1}{1 - x}</tex>,: <tex dpi = "145">1 + x^2 + x^4 + x^6 + \dots = \frac{1}{1-x^2}</tex>: <tex>\dots</tex>: <tex dpi = "145">1 + x^k + x^{2k} + x^{3k} + \dots = \frac{1}{1-x^k}</tex>: <tex>\dots</tex> Запишем теперь [[Производящая функция|производящую функцию]] последовательности <tex>p(n)</tex>:: <tex dpi = "145">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> <tex>(1)</tex> Рассмотрим произведение <tex>(1-x)(1-x^2)(1-x^3)...</tex>, т.е. знаменатель правой части формулы <tex>(1)</tex>. Раскрывая в нём скобки, получим такой следующий результат:
: <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 )''<ref name="pentagon" />, т.е. числа вида <tex>(3q^2 \pm q)/2</tex>, а знаки при соответствующих мономах равны <tex>(-1)^q</tex>. Исходя из этого наблюдения, Эйлер предположил, что должна быть верна:следующая теорема, впоследствии названная его именем.
{{Теорема
Пентагональная теорема Эйлера
| statement =
<texdpi="145"> \prod\limits_{k=1}^\infty \left(1-x^k \right) = \sum\limits_{nq=-\infty}^\infty (-1)^q x^{(\frac{3q^2+q)/}{2}}</tex>
| proof =
}}
Умножим обе части равенства <tex>(1) </tex> на <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> <tex>(2)</tex>
Начнем раскрывать скобки, для наглядности мономы с одинаковыми степенями <tex>x </tex> пишем друг под другом:
: <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> // тут ужасное быдлоформатирование, не знаю как нормально расположить друг под другом
Так как <tex>p(0) = 1</tex>, то оно сокращается с единицей справа. Так что , чтобы выражение <tex>(2) </tex> было удовлетворено при любом <tex>x</tex>, все коэффициенты должны быть равны <tex>0(вроде так)</tex>. Поэтому:
: <tex> p(1) = p(0) </tex>
: <tex> p(2) = p(1) + p(0) </tex>
: <tex> p(4) = p(3) + p(2) </tex>
: <tex> p(5) = p(4) + p(3) - p(0) </tex>
Получаем формулу Эйлера, позволяющую последовательно находить числа <tex>p(n)</tex>:
: <texdpi="145"> p(n) = p(n-1) + p(n-2)+ ... + (-1)^{q+1} (p\left(n - \frac{3q^2 - q}{2}\right) + p\left(n - \frac{3q^2 + q}{2}\right)) </tex>. Асимптотика <tex> O(n \sqrt{n})</tex> получается следующим образом. Так как <tex dpi="145"> n - \frac{3q^2 + q}{2} \geqslant 0 </tex> , то получаем <tex> q </tex> порядка <tex> \sqrt{n} </tex>, а так как находим <tex>n</tex>-е число, то получаем <tex> O(n \sqrt{n}) </tex>. == Примечания ==<references><ref name="amount">[http://oeis.org/A000041 Последовательность 000041 на OEIS]</ref><ref name="pentagon">[http://ru.wikipedia.org/wiki/%D0%A4%D0%B8%D0%B3%D1%83%D1%80%D0%BD%D1%8B%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0#.D0.9F.D1.8F.D1.82.D0.B8.D1.83.D0.B3.D0.BE.D0.BB.D1.8C.D0.BD.D1.8B.D0.B5_.D1.87.D0.B8.D1.81.D0.BB.D0.B0 Википедия {{---}} Пятиугольные числа]</ref><ref name="young">[http://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D0%B7%D0%B1%D0%B8%D0%B5%D0%BD%D0%B8%D0%B5_%D1%87%D0%B8%D1%81%D0%BB%D0%B0#.D0.94.D0.B8.D0.B0.D0.B3.D1.80.D0.B0.D0.BC.D0.BC.D1.8B_.D0.AE.D0.BD.D0.B3.D0.B0 Википедия {{---}} Диаграммы Юнга]</ref></references>
== Используемые материалы Источники информации ==* [http://en.wikipedia.org/wiki/Pentagonal_number_theorem Wikipedia {{---}} Pentagonal number theorem]
* [http://kvant.mirror1.mccme.ru/1988/11/razbienie_chisel.htm Вайнштейн Ф., Разбиение чисел. Журнал "Квант" № 11, 1988 год]
* Н.Я. Виленкин "Комбинаторика", 2007. стр. 138-141. [[httpКатегория://oeis.org/A000041 Последовательность на OEISДискретная математика и алгоритмы]][[Категория: Комбинаторика]]