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

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

Число разбиений $p(n)$ натурального числа n является одним из фундаментальных объектов изучения в теории чисел.

Примеры

Например, $(3,1,1)$ или $(3,2)$ — разбиения числа 5, поскольку $5=3+1+1=3+2$. Всего существует p(5)=7 разбиений числа 5: $(1,1,1,1,1)$, $(2,1,1,1)$, $(2,2,1)$, $(3,1,1)$, $(3,2)$, $(4,1)$, $(5)$.

Некоторые значения числа разбиений $p(n)$ (последовательность A000041 в OEIS) приведены в следующей таблице:

• p(1) = 1
• p(2) = 2
• p(3) = 3
• p(4) = 5
• p(5) = 7
• p(6) = 11
• p(7) = 15
• p(8) = 22
• p(9) = 30
• p(10) = 42
• p(100) = 190 569 292
• p(1000) = 24 061 467 864 032 622 473 692 149 727 991 ( ≈2.4 × 10³¹)

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

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

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

$\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \frac {1}{1-x^k}.$

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

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

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

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

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

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

$\prod_{k=1}^\infty \left(1-x^k \right) = \sum_{q=-\infty}^\infty (-1)^q x^{(3q^2+q)/2}$ .

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

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

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

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

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

$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 < 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 > n, \end{cases}$

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

$P(0, 0) = 1,$

$P(i, 0) = 0$ для всех $i > 0$

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

Количество разбиений натурального числа n на k слагаемых удовлетворяет рекуррентной формуле:

$P(n, k) = P(n-1, k - 1) + P(n - k, k)$

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

$P(i, i) = 1\quad \forall i \in \mathbb{N},$

$P(i, 1) = 1\quad \forall i \in \mathbb{N},$

$P(i, j) = 0\quad \forall j>i.$

Конгруэнтности

Этот раздел статьи ещё не написан. Согласно замыслу одного из участников Википедии, на этом месте должен располагаться специальный раздел. Вы можете помочь проекту, написав этот раздел.

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

Диаграмма Юнга разбиения 10 = 5 + 4 + 1.

Разбиения удобно представлять в виде наглядных геометрических объектов, называемых диаграммами Юнга, в честь английского математика Альфреда Юнга. Диаграмма Юнга разбиения $(k_1, k_2,\dots,k_m)$ — подмножество первого квадранта плоскости, разбитое на ячейки, каждая из которых представляет собой единичный квадрат. Ячейки размещаются в строки, первая строка имеет длину $k_1$, над ней расположена строка длиной $k_2$, и т. д. до $m$-ой строки длины $k_m$. Строки выровнены по левому краю.

Более формально, диаграмма Юнга — это замыкание множества точек $(x,y)$ таких, что

$x,y> 0$ и $y< \sum_{j=[x]}^{m} k_j,$

где $[x]$ обозначает целую часть $x$.

В англоязычной литературе диаграммы Юнга часто изображают отражёнными относительно оси абсцисс.

Схожий объект, называемый диаграммой Ферре, отличается тем, что

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

Применение

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

См. также

• Композиция
• Биномиальный коэффициент
• Теорема Хаусдорфа

Литература

• Эндрюс Г. Теория разбиений. — М.: Наука, 1982. — 255 с.
• Макдональд И. Симметрические функции и многочлены Холла. — М.: Мир, 1985. — 224 с.
• Вайнштейн Ф. В. Разбиение чисел // Квант. — 1988. — № 11. — С. 19-25.
• Фукс Д. О раскрытии скобок, об Эйлере, Гауссе, Макдональде и об упущенных возможностях // Квант. — 1981. — № 8. — С. 12-20.
• Бурман Ю. М. Разбиения и перестановки // Летняя школа «Современная математика». — 2004.