Разбиение числа
Разбие́ние натурального числа́ [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] приведены в следующей таблице[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 | 24061467864032622473692149727991 | |
10000 | 36167251325636293988820471890953695495016030339315650422081868605887952568754066420592310556052906916435144 |
Число разбиений
Производящая функция
Последовательность числа разбиений [math]\displaystyle{ p(n) }[/math] имеет следующую производящую функцию:
Эта формула была открыта Эйлером в 1740 году.
Пентагональная теорема Эйлера
Изучая производящую функцию последовательности [math]\displaystyle{ p(n) }[/math], Эйлер сосредоточил внимание на её знаменателе, то есть на произведении [math]\displaystyle{ (1-x)(1-x^2)(1-x^3)... }[/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] они называются просто пятиугольными.[2]
Из этого наблюдения Эйлер выдвинул предположение о пентагональной теореме:
а впоследствии её доказал. Эта теорема позволяет вычислять числа разбиений при помощи деления формальных степенны́х рядов.
Асимптотические формулы
Асимптотическое выражение для количества разбиений было получено Харди и Рамануджаном в 1918 году, а в 1920 году независимо от них — российским математиком Успенским:[3]
- [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].
Диаграммы Юнга
Разбиения удобно представлять в виде наглядных геометрических объектов, называемых диаграммами Юнга, в честь английского математика Альфреда Юнга . Диаграмма Юнга разбиения [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.