Разбиение числа

Последовательность числа разбиений ${\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})...}$. При раскрытии скобок это бесконечное произведение приобретает следующий вид:

${\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 (-1)^{q}x^{(3q^{2}-q)/2},}$ где ${\displaystyle q}$ пробегает все возможные целые значения, и в этом случае сами числа ${\displaystyle (3q^{2}-q)/2}$ называются обобщёнными пятиугольными. При натуральных ${\displaystyle q}$ они называются просто пятиугольными.[2]

Из этого наблюдения Эйлер выдвинул предположение о пентагональной теореме:

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

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

Асимптотическое выражение для количества разбиений было получено Харди и Рамануджаном в 1918 году, а в 1920 году независимо от них — российским математиком Успенским:[3]

${\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 i\cdot s(m,k)-2\pi in\cdot m/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)}$.