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

Разбиение числа n — это представление n в виде суммы положительных целых чисел, называемых частями. При этом порядок следования частей не учитывается (в отличие от композиций), то есть разбиения, отличающиеся только порядком частей, считаются равными. В канонической записи разбиения части перечисляются в невозрастающем порядке.
Число разбиений p(n) натурального числа n является одним из фундаментальных объектов изучения в теории чисел.

Примеры


 Например, \{3,1,1\} или \{3,2\} — разбиения числа 5, поскольку . Всего существует разбиений числа 5: \{1,1,1,1,1\}, \{2,1,1,1\}, \{2,2,1\}, \{3,1,1\}, \{3,2\}, \{4,1\}, \{5\}.
 Некоторые значения числа разбиений приведены в следующей таблице:
Разбиения
11\{1\}
22\{1,1\}, \{2\}
33\{1,1,1\}, \{2,1\}, \{3\}
45\{1,1,1,1\}, \{2,1,1\}, \{2,2\}, \{3,1\}, \{4\}
57\{1,1,1,1,1\}, \{2,1,1,1\}, \{2,2,1\}, \{3,1,1\}, \{3,2\}, \{4,1\}, \{5\}
611
715
822
930
1042
20627
50
100
1000

Число разбиений


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


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

n=0p(n)xn=k=111xk.
  Эта формула была открыта Эйлером в 1740 году.

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


 Изучая производящую функцию последовательности p(n), Эйлер сосредоточил внимание на её знаменателе, то есть, на произведении (1x)(1x2)(1x3). Это бесконечное произведение при раскрытии скобок приобретает следующий вид:
(1x)(1x2)(1x3)...=1xx2+x5+x7x12x15+x22+x26x35x40+...
 Показатели степеней x в правой части — числа вида (3q2q)/2, где q — целое число, а знак при x(3q2q)/2 равен (1)q. Для натуральных q: (3q2q)/2, это пятиугольные числа.
 Согласно этому наблюдению Эйлер предположил, что должна быть верна Пентагональная теорема:
k=1(1xk)=q=(1)qx(3q2q)/2 .
 Впоследствии эта теорема была Эйлером доказана. Она позволяет вычислять числа разбиений при помощи деления формальных степенных рядов.

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


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

p(n)exp(π23n124)4n3 при n
  дает, например, p(1000)2.44×1031. Уточнение Радемахера представляет число разбиений в виде сходящегося ряда

  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) где

  A\_k(n) = \{sum\_\{0\{le m \textless k \{; ; \{; (m,k)=1\}\{exp \{left(
  \{pi i s(m,k) - 2\{pi inm/k \{right).
 Здесь суммирование ведется по m, взаимно простым с k, а s(m,k) — сумма Дедекинда. Ряд сходится очень быстро.

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


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

  P(n, k) = \{begin\{cases\}
  P(n, k - 1) + P(n - k, k), \& k \{leqslant n,\{\{ P(n, n), \& k \textgreater n, \{end\{cases\} с начальными значениями:

P(0,0)=1,
P(i,0)=0 для всех i>0
  При этом количество всевозможных разбиений числа n равно P(n,n).
 Количество разбиений натурального числа n на k слагаемых удовлетворяет рекуррентной формуле:

P(n,k)=P(n1,k1)+P(nk,k)
  с начальными значениями:
P(i,i)=1iN,

P(i,1)=1iN,

P(i,j)=0j>i.

Диаграммы Юнга


 \textttРазбиения удобно представлять в виде наглядных геометрических объектов, называемых диаграммами Юнга, в честь английского математика \texttt. Диаграмма Юнга разбиения (k1,k2,,km)\texttt — подмножество первого квадранта плоскости, разбитое на ячейки, каждая из которых представляет собой единичный квадрат. Ячейки размещаются в строки, первая строка имеет длину k1\texttt, над ней расположена строка длиной k2\texttt, и т. д. до m\texttt-ой строки длины km\texttt. Строки выровнены по левому краю.
 Более формально, диаграмма Юнга — это замыкание множества точек (x,y) таких, что

x,y>0 и y<j=[x]mkj,
  где [x] обозначает целую часть x.
 В англоязычной литературе диаграммы Юнга часто изображают отражёнными относительно оси абсцисс.
 Схожий объект, называемый диаграммой Феррерса, отличается тем, что

  • вместо ячеек изображаются точки;
  • диаграмма транспонируется: ряды и столбцы меняются местами.

Применение


 Разбиения естественным образом возникают в ряде математических задач. Наиболее значимой из них является теория представлений симметрической группы, где разбиения естественно параметризуют все неприводимые представления. Суммы по всем разбиениям часто встречаются в математическом анализе.