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

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

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

Приклади

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

Деякі значення числа розбиттів $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 624 000 000 000 000 000

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

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

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

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

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

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

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

P(n,k)={\begin{cases}P(n,k-1)+P(n-k,k),&k\leqslant n,\\P(n,n),&k>n,\end{cases}}

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

P(0,0)=1,

P(i,0)=0

для всіх

i>0

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

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

Розбиття зручно представляти у вигляді геометричних об'єктів, які називають діаграмами Юнга, в честь англійського математика Альфреда Юнга. Діаграма Юнга розбиття $(k_{1},k_{2},\ldots ,k_{m})$ — підмножина першого квадранта площини, розбитого на комірки, кожна з яких являє собою одиничний квадрат. Комірки розташовуються в рядочки, перший з них має довжину $k_{1}$ , над нею розташовується рядочок довжиною $k_{2}$ , і т.д. до $m$ -го рядочка довжиною $k_{m}$ .

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

x,y>0

і

y<\sum _{j=[x]}^{m}k_{j},

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

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

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

Литература

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

послідовність A000041 з Онлайн енциклопедії послідовностей цілих чисел, OEIS

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] послідовність A000041 з Онлайн енциклопедії послідовностей цілих чисел, OEIS