Изменения

'''Задача: Дано число ''' По заданному числу <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>.

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

Рассмотрим следующее бесконечное произведение

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

Можно увидеть, что <tex> x^n </tex> встретится в полученной бесконечной сумме столько раз, сколькими способами можно представить <mathtex>n</mathtex> как сумму <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>.

: <texdpi = "145">1 + x + x^2 + x^3 + ... = \frac{1}{1 - x}</tex>,: <texdpi = "145">1 + x^2 + x^4 + x^6 + ... = \frac{1}{1-x^2}</tex>

: <texdpi = "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>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<tex>(1)</tex>

Рассмотрим произведение <tex>(1-x)(1-x^2)(1-x^3)...</tex>, т.е. знаменатель правой части формулы <tex>(1)</tex>. Раскрывая в нём скобки, получим такой следующий результат:

Показатели степеней в правой части — [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 пятиугольные числа''(при чем тут пятиугольники? o_O )''], т.е. числа вида <tex>(3q^2 \pm q)/2</tex>, а знаки при соответствующих мономах равны <tex>(-1)^q</tex>. Исходя из этого наблюдения, Эйлер предположил, что должна быть верна:следующая теорема, впоследствии названная его именем.