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

Разбиение числа 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\}\^\{inftyA\_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 \{leqslantn,\{\{ 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.
 В англоязычной литературе диаграммы Юнга часто изображают отражённымиотносительно оси абсцисс.
 Схожий объект, называемый диаграммой Феррерса, отличается тем,что

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

Применение


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