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

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

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

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

Примеры

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

Некоторые значения числа разбиений ${\displaystyle p(n)}$ приведены в следующей таблице^[1]:

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	24 061 467 864 032 622 473 692 149 727 991
10000	36 167 251 325 636 293 988 820 471 890 953 695 495 016 030 339 315 650 422 081 868 605 887 952 568 754 066 420 592 310 556 052 906 916 435 144

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

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

Последовательность числа разбиений ${\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)}$.

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

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

Диаграмма Юнга формы (5, 4, 1), Французская нотация

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

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

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

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

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

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

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

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

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

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

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

Например, если ${\displaystyle \lambda =(321),\mu =(22)}$, то ${\displaystyle \lambda +\mu =(541),\lambda \cup \mu =(32221).}$

Операции сложения, как и операции умножения, двойственны относительно сопряжения^{[источник не указан 927 дней]}:

${\displaystyle (\lambda \cup \mu )'=\lambda '+\mu '}$;

${\displaystyle (\lambda \times \mu )'=\lambda '\mu '}$.

Порядок

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

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

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

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

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

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

${\displaystyle \lambda \geq \mu \Leftrightarrow \mu '\geq \lambda '.}$

Применение

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

См. также

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