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

Разбие́ние натурального числа́ ${\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]:

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

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

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

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

Разбиения удобно представлять в виде наглядных геометрических объектов, называемых диаграммами Юнга, в честь английского математика Альфреда Юнга^[en]. Диаграмма Юнга разбиения ${\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).}$

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

${\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 '.}$

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

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

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

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

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

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

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