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

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

Число розбиттів $p(n)$ натурального числа $n$ є одним із фундаментальних об'єктів вивчення в теорії чисел.

Приклади

Наприклад, Шаблон:Nobr} або Шаблон:Nobr} — розбиття числа 5, оскільки Шаблон:Nobr. Всього існує $p(5)=7$ розбиттів числа 5: Шаблон:Nobr}, Шаблон:Nobr}, Шаблон:Nobr}, Шаблон:Nobr}, Шаблон:Nobr}, Шаблон:Nobr}, {5}.

Деякі значення числа розбиттів $p(n)$ наведені в наступній таблиці:

Шаблон:Mvar	Шаблон:Mvar(Шаблон:Mvar)	Розбиття
1	1	{1}
2	2	Шаблон:Nobr}, {2}
3	3	Шаблон:Nobr}, Шаблон:Nobr}, {3}
4	5	Шаблон:Nobr}, Шаблон:Nobr}, Шаблон:Nobr}, Шаблон:Nobr}, {4}
5	7	Шаблон:Nobr}, Шаблон:Nobr}, Шаблон:Nobr}, Шаблон:Nobr}, Шаблон:Nobr}, Шаблон:Nobr}, {5}
6	11
7	15
8	22
9	30
10	42
20	627
50	Шаблон:Num
100	Шаблон:Num
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

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

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

Послідовність числа розбиттів $p(n)$ має наступну твірну функцію:

$\sum _{n=0}^{\mathrm{\infty }}p(n)x^n=\prod _{k=1}^{\mathrm{\infty }}\frac{1}{1-x^k}.$

Формула була відкрита Ейлером в 1740 році.

Рекурентні формули

Кількість розбиттів числа $n$ на доданки, що не перевищують $k$, задовольняє формулу:

$P(n,k)=\{\begin{array}{cc}P(n,k-1)+P(n-k,k),& k⩽n,\\ P(n,n),& k>n,\end{array}$

з початковими значення:

$P(0,0)=1,$

$P(i,0)=0$ для всіх $i>0$

При цьому кількість всеможливих розбиттів числа $n$ дорівнює $P(n,n)$.

Діаграма Юнга

Шаблон:Main Розбиття зручно представляти у вигляді геометричних об'єктів, які називають діаграмами Юнга, в честь англійського математика Альфреда Юнга. Діаграма Юнга розбиття $(k_1,k_2,\dots ,k_m)$ — підмножина першого квадранта площини, розбитого на комірки, кожна з яких являє собою одиничний квадрат. Комірки розташовуються в рядочки, перший з них має довжину $k_1$, над нею розташовується рядочок довжиною $k_2$, і т.д. до $m$-го рядочка довжиною $k_m$.

Більш формально, діаграма Юнга — це замикання множини точок $(x,y)$ таких, що

$x,y>0$ і $y<\sum _{j=[x]}^m{k}_j,$

де $[x]$ означає цілу частину $x$.

Спряженим (або транспонованим) розбиттям до $\lambda$ називають розбиття, діаграма Юнга якого є діаграмою Юнга розбиття $\lambda$, відображеною відносно прямої $y=x$. Наприклад, спряженим до розбиття (6,4,4,1) буде розбиття (4,3,3,3,1,1). Спряжене розбиття позначається ${\lambda }^{\prime }$.

Діаграма Феррерса

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

Такий об'єкт, званий діаграмою Шаблон:Iw2, відрізняється тим, що

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

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

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

Література

• Эндрюс Г. Теория разбиений. — М.: Наука, 1982. — 255 с.
• Макдональд И. Симметрические функции и многочлены Холла. — М.: Мир, 1985. — 224 с.
• Шаблон:Статья
• Шаблон:Статья
• Новая теория доказывает природу цифр Шаблон:Webarchive.
• Шаблон:Статья