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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Если , то соответствующее этому набору чисел разбиение обычно обозначается как {} = . Число при этом называют мощностью разбиения и обозначают , а число называют длиной разбиения и обозначают .

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

Примеры[править | править код]

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

Некоторые значения числа разбиений приведены в следующей таблице[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

Число разбиений[править | править код]

Производящая функция[править | править код]

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

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

Пентагональная теорема Эйлера[править | править код]

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

В правой части слагаемые имеют вид где  пробегает все возможные целые значения, и в этом случае сами числа называются обобщёнными пятиугольными. При натуральных они называются просто пятиугольными.[2]

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

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

Асимптотические формулы[править | править код]

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

при

Например, .

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

где

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

Рекуррентные формулы[править | править код]

Количество разбиений числа на слагаемые, не превышающие , удовлетворяет рекуррентной формуле:

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

для всех

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

Диаграммы Юнга[править | править код]

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

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

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

и

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

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

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

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

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

Сумма и произведение разбиений[править | править код]

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

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

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

;
.

Порядок[править | править код]

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

Лексикографический порядок. Говорят, что старше по лексикографическому порядку, если существует такое натуральное , что для каждого , а также .

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

Естественный (частичный) порядок. Говорят, что старше по естественному порядку (обозначается ), если для каждого выполняется неравенство .

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

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

Применение[править | править код]

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

См. также[править | править код]

Примечания[править | править код]

  1. Последовательность A000041 в OEIS
  2. Табачников С. Л., Фукс Д. Б. Математический дивертисмент. — МЦНМО, 2011. — ISBN 978-5-94057-731-7.
  3. Uspensky, Asymptotic Formulae for Numerical Functions Which Occur in the Theory of Partitions, Bull. Acad. Sci. URSS 14, 1920, S. 199–218

Литература[править | править код]