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

Разбие́ние натурального числа́ [math]\displaystyle{ n }[/math] — это такое представление числа [math]\displaystyle{ n }[/math] в виде суммы положительных целых чисел [math]\displaystyle{ \lambda_1+\lambda_2+\dots+\lambda_m }[/math], которое, в отличие от композиции, не учитывает порядок слагаемых. Слагаемые [math]\displaystyle{ \lambda_k }[/math] в разбиении называются частями. В канонической записи разбиения слагаемые перечисляются в невозрастающем порядке.

Если [math]\displaystyle{ \lambda_1 \ge \lambda_2 \dots \ge \lambda_m }[/math], то соответствующее этому набору чисел разбиение обычно обозначается как {[math]\displaystyle{ \lambda_1, \lambda_2, \dots \lambda_m }[/math]} = [math]\displaystyle{ \lambda }[/math]. Число [math]\displaystyle{ n }[/math] при этом называют мощностью разбиения и обозначают [math]\displaystyle{ |\lambda| }[/math], а число [math]\displaystyle{ m }[/math] называют длиной разбиения и обозначают [math]\displaystyle{ l(\lambda) }[/math].

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

Примеры

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

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

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

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

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

Последовательность числа разбиений [math]\displaystyle{ p(n) }[/math] имеет следующую производящую функцию:

[math]\displaystyle{ \sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \frac {1}{1-x^k}. }[/math]

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

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

Изучая производящую функцию последовательности [math]\displaystyle{ p(n) }[/math], Эйлер сосредоточил внимание на её знаменателе, то есть на произведении [math]\displaystyle{ (1-x)(1-x^2)(1-x^3)... }[/math]. При раскрытии скобок это бесконечное произведение приобретает следующий вид:

[math]\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 }[/math]

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

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

[math]\displaystyle{ \prod_{k=1}^\infty \left(1-x^k \right) = \sum_{q=-\infty}^\infty (-1)^q x^{(3q^2-q)/2}, }[/math]

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

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

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

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

Например, [math]\displaystyle{ p(1000)\approx 2{,}44\cdot 10^{31} }[/math].

Впоследствии Харди и Рамануджан нашли более точное выражение в виде суммы, а Радемахер вывел точный сходящийся ряд, по которому можно находить сколь угодно близкие асимптотические представления:

[math]\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), }[/math]

где

[math]\displaystyle{ A_k(n) = \sum_{\begin{smallmatrix}0\leqslant m\lt k\\(m,k)=1\end{smallmatrix}}\exp \left( \pi i\cdot s(m,k) - 2\pi in\cdot m/k \right). }[/math]

Здесь суммирование ведётся по [math]\displaystyle{ m }[/math], взаимно простым с [math]\displaystyle{ k }[/math], а [math]\displaystyle{ s(m,k) }[/math] — сумма Дедекинда. Ряд сходится очень быстро.

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

Количество разбиений числа [math]\displaystyle{ n }[/math] на слагаемые, не превышающие [math]\displaystyle{ k }[/math], удовлетворяет рекуррентной формуле:

[math]\displaystyle{ P(n,\; k) = \begin{cases} P(n,\; k - 1) + P(n - k,\; k), & k \leqslant n,\\ P(n,\; n), & k \gt n, \end{cases} }[/math]

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

[math]\displaystyle{ P(0,\; 0) = 1, }[/math]

[math]\displaystyle{ P(i,\; 0) = 0 }[/math] для всех [math]\displaystyle{ i \gt 0 }[/math]

При этом количество всевозможных разбиений числа [math]\displaystyle{ n }[/math] равно [math]\displaystyle{ P(n,\; n) }[/math].

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

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

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

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

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

[math]\displaystyle{ x,\ y\gt 0 }[/math] и [math]\displaystyle{ y\lt \sum_{j=[x]}^{m} k_j, }[/math]

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

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

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

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

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

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

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

• [math]\displaystyle{ \lambda + \mu }[/math]: [math]\displaystyle{ (\lambda + \mu)_i= \lambda_i + \mu_i }[/math];
• [math]\displaystyle{ \lambda \cup \mu }[/math]: разбиение, содержащее части [math]\displaystyle{ \lambda }[/math] и [math]\displaystyle{ \mu }[/math] в порядке нестрогого убывания;
• [math]\displaystyle{ \lambda\mu }[/math]: [math]\displaystyle{ (\lambda \mu)_i= \lambda_i \mu_i }[/math];
• [math]\displaystyle{ \lambda \times \mu }[/math]: разбиение, содержащее части [math]\displaystyle{ min(\lambda_i, \mu_j) }[/math] для всех [math]\displaystyle{ i \le l(\lambda) }[/math] и всех [math]\displaystyle{ j \le l(\mu) }[/math] в порядке нестрогого убывания.

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

[math]\displaystyle{ (\lambda \cup \mu)' = \lambda' + \mu' }[/math];

[math]\displaystyle{ (\lambda \times \mu)' = \lambda' \mu' }[/math].

Порядок

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

Лексикографический порядок. Говорят, что [math]\displaystyle{ \lambda }[/math] старше [math]\displaystyle{ \mu }[/math] по лексикографическому порядку, если существует такое натуральное [math]\displaystyle{ k }[/math], что [math]\displaystyle{ \lambda_i = \mu_i }[/math] для каждого [math]\displaystyle{ i\lt k }[/math], а также [math]\displaystyle{ \lambda_k \gt \mu_k }[/math].

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

Естественный (частичный) порядок. Говорят, что [math]\displaystyle{ \lambda }[/math] старше [math]\displaystyle{ \mu }[/math] по естественному порядку (обозначается [math]\displaystyle{ \lambda \ge \mu }[/math]), если для каждого [math]\displaystyle{ i \ge 1 }[/math] выполняется неравенство [math]\displaystyle{ \lambda_1 + \lambda_2 + \dots + \lambda_i \ge \mu_1 + \mu_2 + \dots + \mu_i }[/math].

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

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

[math]\displaystyle{ \lambda \ge \mu \Leftrightarrow \mu' \ge \lambda'. }[/math]

Применение

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

См. также

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

Литература

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