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

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

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

Примеры

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

Некоторые значения числа разбиений (последовательность 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³¹)

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

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

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

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

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

Изучая производящую функцию последовательности , Эйлер сосредоточил внимание на её знаменателе, то есть, на произведении . Это бесконечное произведение при раскрытии скобок приобретает следующий вид:

Показатели степеней x в правой части — это пятиугольные числа, то есть, числа вида где q — целое число, а знак при равен .

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

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

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

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

при

дает, например, . Уточнение Радемахера представляет число разбиений в виде сходящегося ряда

$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).$

Здесь суммирование ведется по , взаимно простым с , а — сумма Дедекинда. Ряд сходится очень быстро.

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

Количество разбиений числа 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}$

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

для всех

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

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

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

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

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

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

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

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

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

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

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

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

Применение

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

См. также

Литература

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

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

Light-industry-up.ru

Экосистема промышленности

Публикации