Розбиття числа

Розбиття числа ${\displaystyle n}$ — це представлення ${\displaystyle n}$ у вигляді суми додатних цілих чисел, які називають частинами. При цьому порядок слідування частин не враховується, тобто розбиття, які відрізняються лише порядком частин, вважаються рівними.

Число розбиттів ${\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 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)}$.

Розбиття зручно представляти у вигляді геометричних об'єктів, які називають діаграмами Юнга, в честь англійського математика Альфреда Юнга. Діаграма Юнга розбиття ${\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 '}$.

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

Такий об'єкт, званий діаграмою Феррерса^[en], відрізняється тим, що

• замість комірок зображуються крапки;
• діаграма транспонується: рядки та стовпці міняються місцями.

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

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