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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Разбие́ние числа́ 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 622 473 692 149 727 991

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

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

Последовательность числа разбиений p(n) имеет следующую производящую функцию:

\sum_{n=0}^\infty p(n)x^n = \prod_{k=1}^\infty \frac {1}{1-x^k}.

Эта формула была открыта Эйлером в 1740 году.

Пентагональная теорема Эйлера[править | править вики-текст]

Изучая производящую функцию последовательности p(n), Эйлер сосредоточил внимание на её знаменателе, то есть, на произведении (1-x)(1-x^2)(1-x^3)\ldots. Это бесконечное произведение при раскрытии скобок приобретает следующий вид:

(1 - x)(1 - x^2)(1 - x^3) ... = 1 - x - x^2 + x^5 + x^7 - x^{12} - x^{15} + x^{22} + x^{26} - x^{35} - x^{40} + ...

Показатели степеней x в правой части — это пятиугольные числа, то есть, числа вида (3q^2 + q)/2, где qцелое число, а знак при x^{(3q^2 + q)/2} равен (-1)^q.

Согласно этому наблюдению Эйлер предположил, что должна быть верна Пентагональная теорема:

 \prod_{k=1}^\infty \left(1-x^k \right) = \sum_{q=-\infty}^\infty (-1)^q x^{(3q^2+q)/2} .

Впоследствии эта теорема была Эйлером доказана. Она позволяет вычислять числа разбиений при помощи деления формальных степенны́х рядов.

Асимптотические формулы[править | править вики-текст]

Асимптотическое выражение для количества разбиений было получено Харди и Рамануджаном и впоследствии уточнено Радемахером. Оригинальное выражение Харди — Рамануджана[источник не указан 1276 дней]

p(n) \sim \frac {\exp \left( \pi \sqrt {\frac {2}{3}} \sqrt {n-\frac{1}{24}}\right) } {4n\sqrt{3}}  при  n\rightarrow \infty

дает, например, p(1000)\approx 2.44\times 10^{31}. Уточнение Радемахера представляет число разбиений в виде сходящегося ряда

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)

где

A_k(n) = \sum_{0\le m < k \; ; \; (m,k)=1}\exp \left( 
\pi i s(m,k) - 2\pi inm/k \right).

Здесь суммирование ведется по m, взаимно простым с k, а s(m,k)сумма Дедекинда. Ряд сходится очень быстро.

Рекуррентные формулы[править | править вики-текст]

Количество разбиений числа 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).

Количество разбиений натурального числа n на k слагаемых удовлетворяет рекуррентной формуле:

P(n, k) = P(n-1, k - 1) + P(n - k, k)

с начальными значениями:

P(i, i) = 1\quad \forall i \in \mathbb{N},
P(i, 1) = 1\quad \forall i \in \mathbb{N},
P(i, j) = 0\quad \forall j>i.

Конгруэнтности[править | править вики-текст]

Диаграммы Юнга[править | править вики-текст]

Диаграмма Юнга разбиения 10 = 5 + 4 + 1.

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

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

Схожий объект, называемый диаграммой Феррерса, отличается тем, что

  • вместо ячеек изображаются точки;
  • диаграмма транспонируется: ряды и столбцы меняются местами.

Применение[править | править вики-текст]

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

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

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

  1. Последовательность A000041 в OEIS

Литература[править | править вики-текст]