Изменения
Нет описания правки
'''Задача:''' По заданному числу <tex>n</tex> найти [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__
После раскрытия скобок каждый член произведения получается в результате умножения мономов (одночленов), взятых по одному из каждой скобки. Если в первой скобке взять <tex dpi = "145">x^{m_1}</tex>, во второй — <tex dpi = "145">x^{2m_2}</tex> и т.д., то их произведение будет равно <tex dpi = "145">x^{m_1 + 2m_2 + 3m_3 + \dots}.</tex> Значит, после раскрытия скобок получится сумма мономов вида <tex dpi = "145">x^{m_1 + 2m_2 + 3m_3 + \dots}</tex>.
Можно увидеть, что <tex> x^n </tex> встретится в полученной бесконечной сумме столько раз, сколькими способами можно представить <tex>n</tex> как сумму <tex>m_1 + 2m_2 + 3m_3 + ...</tex> Каждому такому представлению отвечает разбиение числа <tex>n</tex> на <tex>m_1</tex> единиц, <tex>m_2</tex> двоек и т.д. Таким образом , очевидно , получаются все разбиения, так как из первой скобки мы можем взять любое <tex>x^{m_i}</tex>, где <tex>m_i \in [0 \dots \infty),</tex> то есть произвольное количество единиц в нашем разбиении. Аналогично, мы можем взять произвольное количество двоек и т.д. Но при раскрытии скобок мы находим произведения всех возможных комбинации множителей из разных скобок. Поэтому коэффициент при <tex>x^n</tex> равен числу разбиений <tex>p(n)</tex>.
Посмотрим теперь на выражения в скобках. Каждое из них — бесконечная геометрическая прогрессия. По формуле ее суммирования:
Точно такое же преобразование можно сделать, если диаграмма состоит из одной трапеции, но <tex>n \geq m+1</tex>. Стираем верхнюю строку и к нижним <tex>n-1</tex> строчкам приписываем <tex>m</tex> точек.
'''Преобразование 2.'''Пусть теперь диаграмма опять содержит не менее двух трапеций, но <tex>m \b > n</tex>. Тогда от каждой строки последней трапеции возьмем по одной точке и составим из них первую строку (из <tex> n </tex> точек) новой диаграммы. Это можно сделать, так как <tex>m \b > n</tex>, и поэтому составленная строка короче первой строки исходной диаграммы. Кроме того, так как мы взяли все строки будут иметь различную длину. Наконец, новая диаграмма содержит столько же точек, что и исходная, но четность числа строк изменилась - новая диаграмма содержит еще одну строку.
Преобразование 2 допускают и диаграммы, состоящие из одной трапеции, если <tex>n \leq m - 2</tex> (появляющаяся первая строка состоит из <tex>n</tex> точек, она должна быть короче бывшей первой строки, уменьшившейся до <tex>m-1</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(n)</tex>:
: <tex> 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> n - \frac{3q^2 + q}{2} \ge 0 </tex> , то получаем <tex> q </tex> порядка <tex> \sqrt{n} </tex>, а так как находим n-е число, то получаем <tex> O(n \sqrt{n}) </tex>.
== Используемые материалы ==
