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

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

Разбие́ние числа́ $n$ — это способ записать натуральное число $n$ в виде суммы натуральных чисел. При этом порядок слагаемых не учитывается, то есть способы, отличающиеся только порядком слагаемых, считаются одним разбиением. Если порядок учитывается, то говорят о композициях числа $n$ . Для разбиений можно выбрать любой порядок слагаемых; канонической считается запись в виде невозрастающей последовательности положительных целых.

[править] Примеры

Например, $(3,1,1)$ или $(3,2)$ — разбиения числа 5, поскольку $5 = 3 + 1 + 1 = 3 + 2$ . Всего есть 7 разбиений числа 5: $(1,1,1,1,1)$ , $(2,1,1,1)$ , $(2,2,1)$ , $(3,1,1)$ , $(3,2)$ , $(4,1)$ , $(5)$ .

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

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

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

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

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

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

(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 + ...

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

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

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

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

[править] Примеры

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

p(1) = 1
p(2) = 2
p(3) = 3
p(4) = 5
p(5) = 7
p(6) = 11
p(7) = 15
p(8) = 22
p(9) = 30
p(10) = 42
p(100) = 190 569 292
p(1000) = 24 061 467 864 032 622 473 692 149 727 991 ( ≈2.4 × 10³¹)

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

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

$p(n) \sim \frac {\exp \left( \pi \sqrt {2n/3}\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)$ — сумма Дедекинда. Ряд сходится очень быстро.

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

Этот раздел статьи ещё не написан.

Согласно замыслу одного из участников Википедии, на этом месте должен располагаться специальный раздел.
Вы можете помочь проекту, написав этот раздел.

[править] Диаграммы Юнга

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

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

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

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

[править] Применение

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

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

Композиция

[править] Литература

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