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

Разбие́ние натурального числа́ $n$ — это такое представление числа $n$ в виде суммы положительных целых чисел $\lambda _{1}+\lambda _{2}+\dots +\lambda _{m}$, которое, в отличие от композиции, не учитывает порядок слагаемых. Слагаемые $\lambda _{k}$ в разбиении называются частями. В канонической записи разбиения слагаемые перечисляются в невозрастающем порядке.

Если $\lambda _{1}\geq \lambda _{2}\dots \geq \lambda _{m}$, то соответствующее этому набору чисел разбиение обычно обозначается как {$\lambda _{1},\lambda _{2},\dots \lambda _{m}$} = $\lambda$. Число $n$ при этом называют мощностью разбиения и обозначают $|\lambda |$, а число $m$ называют длиной разбиения и обозначают $l(\lambda )$.

Число разбиений $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)$ приведены в следующей таблице:

n	p(n)	Разбиения
1	1	{1}
2	2	{2}, {1, 1}
3	3	{3}, {2, 1}, {1, 1, 1}
4	5	{4}, {3, 1}, {2, 2}, {2, 1, 1}, {1, 1, 1, 1}
5	7	{5}, {4, 1}, {3, 2}, {3, 1, 1}, {2, 2, 1}, {2, 1, 1, 1}, {1, 1, 1, 1, 1},
6	11
7	15
8	22
9	30
10	42
20	627
50	204 226
100	190 569 292
1000	24061467864032622473692149727991
10000	36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144

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

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

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

$(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$

В правой части слагаемые имеют вид $(-1)^{q}x^{(3q^{2}-q)/2},$ где $q$ пробегает все возможные целые значения, и в этом случае сами числа $(3q^{2}-q)/2$ называются обобщёнными пятиугольными. При натуральных $q$ они называются просто пятиугольными.

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

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

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

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

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

$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\cdot 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 _{\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).$

Здесь суммирование ведётся по $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)$.

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

Основная статья: Диаграмма Юнга

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

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

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

$x,\ y>0$ и $y<\sum _{j=[x]}^{m}k_{j},$

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

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

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

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

Сопряженным (или транспонированным) разбиением к $\lambda$ называется разбиение, чья диаграмма Юнга является диаграммой Юнга разбиения $\lambda$, отражённая относительно прямой $y=x$. Например, сопряжённым к разбиению (6,4,4,1) будет разбиение (4,3,3,3,1,1). Сопряжённое разбиение обозначается $\lambda '$.

Сумма и произведение разбиений

Пусть имеются два разбиения $\lambda$ и $\mu$. Тогда для них определены следующие операции:

• $\lambda +\mu$: $(\lambda +\mu )_{i}=\lambda _{i}+\mu _{i}$;
• $\lambda \cup \mu$: разбиение, содержащее части $\lambda$ и $\mu$ в порядке нестрогого убывания;
• $\lambda \mu$: $(\lambda \mu )_{i}=\lambda _{i}\mu _{i}$;
• $\lambda \times \mu$: разбиение, содержащее части $min(\lambda _{i},\mu _{j})$ для всех $i\leq l(\lambda )$ и всех $j\leq l(\mu )$ в порядке нестрогого убывания.

Операции сложения, как и операции умножения, двойственны относительно сопряжения:

$(\lambda \cup \mu )'=\lambda '+\mu '$;

$(\lambda \times \mu )'=\lambda '\mu '$.

Порядок

Пусть имеются два разбиения $\lambda$ и $\mu$ числа $n$.

Лексикографический порядок. Говорят, что $\lambda$ старше $\mu$ по лексикографическому порядку, если существует такое натуральное $k$, что $\lambda _{i}=\mu _{i}$ для каждого $i<k$, а также $\lambda _{k}>\mu _{k}$.

В таблице выше разбиения расположены в лексикографическом порядке.

Естественный (частичный) порядок. Говорят, что $\lambda$ старше $\mu$ по естественному порядку (обозначается $\lambda \geq \mu$), если для каждого $i\geq 1$ выполняется неравенство $\lambda _{1}+\lambda _{2}+\dots +\lambda _{i}\geq \mu _{1}+\mu _{2}+\dots +\mu _{i}$.

Начиная с n=6 можно найти разбиения, которые невозможно сравнить в этом смысле. Например, (3, 1, 1, 1) и (2, 2, 2).

Для естественного порядка выполняется эквивалентность:

$\lambda \geq \mu \Leftrightarrow \mu '\geq \lambda '.$

Применение

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

См. также

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

Литература

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