Изменения

<tex> \prod\limits_{k=1}^\infty \left(1-x^k \right) = \sum\limits_{q=-\infty}^\infty (-1)^q x^{(\frac{3q^2+q)/}{2}}</tex>

Пентагональная теорема оказалась «крепким орешком» — <tex>A = (1-x)(1-x^2)(1-x^3)...(1-x^n)...</tex> Раскроем в этом произведении первые 22 скобки. Мы получим выражение  <tex>A = [1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+...]\times(1-x^{23})(1-x^{24})...(1-x^n)...</tex>, где в квадратной скобке точками обозначены слагаемые, содержащие <tex>x</tex> в более высокой степени, чем 22. Не будем выписывать эти члены, так как после умножения квадратной скобки на <tex>1-x^{23}</tex>, <tex>1-x^{24}</tex> и т.д. они изменятся. Выписанные же члены больше меняться не будут. Поэтому, если раскрыть все скобки, то получится бесконечный ряд, первые члены которого имеют вид <tex>A=1-x-x^2+x^5+x^7-x^{12}-x^{15}+x^{22}+...</tex> Анализируя этот ряд, Эйлер сумел доказать её пришел к выводу, что, если превратить бесконечное произведение  <tex>A = (1-x)(1-x^2)(1-x^3)...(1-x^n)...</tex> в ряд, то в этом ряду отличны от нуля лишь 14 лет спустяслагаемые, вида <tex>(-1)^q x^{\frac{3q^2+q}{2}}</tex>, где <tex>q</tex> - натуральное число. При раскрытии скобок в исходном произведении слагаемое <tex>\pm x^N</tex> встретится столько раз, сколькими способами можно разбить число <tex>N</tex> на различные слагаемые. При этом, если число слагаемых четно, то появляется <tex>x^N</tex>, а если это число нечетно, то появляется <tex>-x^N</tex>.Например, разбиению <tex>12=5+4+2+1</tex> - соответствует слагаемое <tex>(-x^5)(-x^4)(-x^2)(-x^1)=x^{12},</tex> а разбиению <tex>12=5+4+3</tex> - слагаемое <tex>(-x^5)(-x^4)(-x^3)=-x^{12}</tex>. Таким образом, коэффициент при <tex>x^N</tex> в разложении <tex>A</tex> в ряд равен разности между количеством разбиений <tex>N</tex> на четное число различных слагаемых и количеством разбиений <tex>N</tex> на нечетное число различных слагаемых. Тогда теорему можно переформулировать следующим образом: {{TODOТеорема| about = Переформулировка пентагональной теоремы| statement = Если число <tex>N</tex> не может быть представлено в виде <tex>N =\frac{3q^2+q}{2}</tex>, то оно имеет одинаковое количество разбиений на четное и на нечетное число различных слагаемых. А для чисел вида <tex>N =\frac{3q^2+q}{2}</tex> разность между этими количествами равна <tex>(-1)^q</tex>.}} Иными словами, если <tex>q</tex> четно, то на одно больше разбиений на четное число слагаемых, а если <tex>q</tex> нечетно, то на одно больше разбиений на нечетно число слагаемых. Докажем эту теорему с помощью [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 диаграмм Юнга].. Покажем несколько способов превращения диаграммы с четным числом строк диаграмму из стольких же точек с нечетным числом строк и обратно. Так как мы рассматриваем лишь разбиения на различные слагаемые, то диаграммы таких разбиений состоят из нескольких трапеций, поставленных друг на друга. Обозначим число точек в верхней строке диаграммы через <tex>m</tex>, а число строк нижней трапеции через <tex>n</tex> (на рис. 1 слева изображена диаграмма, для которой <tex>m=2</tex>, <tex>n=3</tex>).[[Файл:Diagramma_2_3.jpg| t thumb|right|Рис. 1. m = скурить доказательство2, n = 3]] '''Преобразование 1.''' Предположим, что диаграмма содержит не менее двух трапеций, причем <tex>m\leq n</tex>. В этом случае отбросим первую строку из <tex>m</tex> точек, но удлиним последние <tex>m</tex> строк нижней трапеции на одну точку(рис. 1). После этого общее число точек не изменится, все строки окажутся различной длины, но четность числа строк изменится. Точно такое же преобразование можно сделать, если диаграмма состоит из одной трапеции, но <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>N</tex>, допускающие одно из этих преобразований, распадаются на пары диаграмм с четным и нечетным числом строк, поэтому их одинаковое число. Осталось выяснить, какие же диаграммы не допускают ни одного из описанных преобразований. Ясно, что эти диаграммы состоят из одной трапеции, причем для них либо <tex>m=n</tex>, либо <tex>m=n+1</tex>. В первом случае диаграмма содержит <tex>n+(n+1)+(n+2)+\dots+(2n-1)=\frac{3n^2-n}{2}</tex> точек, а во втором - на <tex>n</tex> точек больше, т.е. <tex>\frac{3n^2+n}{2}</tex>. Приведенные рассуждения показывают, что если <tex>N</tex> не является числом вида <tex>\frac{3n^2 \pm n}{2}</tex>, то оно имеет поровну разбиений на четное и нечетное число различных слагаемых. Очевидно также, что равенства <tex>N=\frac{3n^2+n}{2}</tex> и <tex>N=\frac{3l^2-l}{2}</tex> одновременно выполняться не могут, поэтому если <tex>N=\frac{3n^2\pm n}{2}</tex>, то без пары останется ровно одна диаграмма, не допускающая преобразования и имеющая <tex>n</tex> строк (слагаемых <tex>N</tex>). Если <tex>n</tex> - четное число, то разбиений на четное число слагаемых окажется на 1 больше, чем на нечетное число слагаемых. Если же <tex>n</tex> - нечетное число, то на 1 больше будет разбиений на нечетное число слагаемых. Теорема доказана. 

: <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>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(2)

::: &nbsp;&nbsp;&nbsp;&nbsp;<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>::::: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <tex> - p(0) x^2 - p(1) x^3 - p(2) x^4 - p(3) x^5 - p(4) x^6 - \dots </tex>::::::::::::: &nbsp;<tex>+ p(0) x^5 + p(1) x^6 + \dots </tex> // тут ужасное быдлоформатирование, не знаю как нормально расположить друг под другом

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

Ну и объяснение асимптотики Асимптотика <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>.