WikiSort.ru - Не сортированное

Производящая функция

Последовательность числа разбиений ${\displaystyle p(n)}$ имеет следующую производящую функцию:

${\displaystyle \sum _{n=0}^{\infty }p(n)x^{n}=\prod _{k=1}^{\infty }{\frac {1}{1-x^{k}}}.}$

Эта формула была открыта Эйлером в 1740 году.

Пентагональная теорема Эйлера

Изучая производящую функцию последовательности ${\displaystyle p(n)}$ , Эйлер сосредоточил внимание на её знаменателе, то есть, на произведении ${\displaystyle (1-x)(1-x^{2})(1-x^{3})\ldots }$ . Это бесконечное произведение при раскрытии скобок приобретает следующий вид:

${\displaystyle (1-x)(1-x^{2})(1-x^{3})\ldots =1-x-x^{2}+x^{5}+x^{7}-x^{12}-x^{15}+x^{22}+x^{26}-x^{35}-x^{40}+\ldots }$

Показатели степеней ${\displaystyle x}$ в правой части — числа вида ${\displaystyle (3q^{2}-q)/2,}$ где ${\displaystyle q}$  — целое число, а знак при ${\displaystyle x^{(3q^{2}-q)/2}}$ равен ${\displaystyle (-1)^{q}}$ . Для натуральных ${\displaystyle q}$ : ${\displaystyle (3q^{2}-q)/2}$  — это пятиугольные числа.^[2]

Согласно этому наблюдению, Эйлер предположил, что должна быть верна Пентагональная теорема:

${\displaystyle \prod _{k=1}^{\infty }\left(1-x^{k}\right)=\sum _{q=-\infty }^{\infty }(-1)^{q}x^{(3q^{2}-q)/2}}$ .

Впоследствии эта теорема была доказана Эйлером. Она позволяет вычислять числа разбиений при помощи деления формальных степенны́х рядов.

Асимптотические формулы

Асимптотическое выражение для количества разбиений было получено Харди и Рамануджаном и впоследствии уточнено Радемахером. Оригинальное выражение Харди — Рамануджана^{[источник не указан 2278 дней]}

${\displaystyle p(n)\sim {\frac {\exp \left(\pi {\sqrt {\frac {2}{3}}}{\sqrt {n-{\frac {1}{24}}}}\right)}{4n{\sqrt {3}}}}}$ при ${\displaystyle n\rightarrow \infty }$

даёт, например, ${\displaystyle p(1000)\approx 2{,}44\cdot 10^{31}}$ . Уточнение Радемахера представляет число разбиений в виде сходящегося ряда

${\displaystyle p(n)={\frac {1}{\pi {\sqrt {2}}}}\sum _{k=1}^{\infty }A_{k}(n)\;{\sqrt {k}}\;{\frac {d}{dn}}\left({\frac {\sinh \left({\frac {\pi }{k}}{\sqrt {{\frac {2}{3}}\left(n-{\frac {1}{24}}\right)}}\right)}{\sqrt {n-{\frac {1}{24}}}}}\right),}$

где

${\displaystyle A_{k}(n)=\sum _{\begin{smallmatrix}0\leqslant m<k\\(m,\;k)=1\end{smallmatrix}}\exp \left(\pi is(m,\;k)-2\pi inm/k\right).}$

Здесь суммирование ведётся по ${\displaystyle m}$ , взаимно простым с ${\displaystyle k}$ , а ${\displaystyle s(m,\;k)}$  — сумма Дедекинда. Ряд сходится очень быстро.

Рекуррентные формулы

Количество разбиений числа ${\displaystyle n}$ на слагаемые, не превышающие ${\displaystyle k}$ , удовлетворяет рекуррентной формуле:

${\displaystyle P(n,\;k)={\begin{cases}P(n,\;k-1)+P(n-k,\;k),&k\leqslant n,\\P(n,\;n),&k>n,\end{cases}}}$

с начальными значениями:

${\displaystyle P(0,\;0)=1,}$

${\displaystyle P(i,\;0)=0}$ для всех ${\displaystyle i>0}$

При этом количество всевозможных разбиений числа ${\displaystyle n}$ равно ${\displaystyle P(n,\;n)}$ .