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

Розбиття числа ${\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]:

n	p(n)	Розбиття
1	1	{1}
2	2	{1, 1}, {2}
3	3	{1, 1, 1}, {2, 1}, {3}
4	5	{1, 1, 1, 1}, {2, 1, 1}, {2, 2}, {3, 1}, {4}
5	7	{1, 1, 1, 1, 1}, {2, 1, 1, 1}, {2, 2, 1}, {3, 1, 1}, {3, 2}, {4, 1}, {5}
6	11
7	15
8	22
9	30
10	42
20	627
50	204 226
100	190 569 292
1000	24 061 467 864 032 622 473 692 149 727 991
10000	36 167 251 325 636 293 988 820 471 890 953 695 495 016 030 339 315 650 422 081 868 605 887 952 568 754 066 420 592 310 556 052 906 916 435 144

Число розбиттів

Твірна функція

Послідовність числа розбиттів ${\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], відрізняється тим, що

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

Застосування

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