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

Разбиение числа n {displaystyle n} — это представление n {displaystyle n} в виде суммы положительных целых чисел, называемых частями. При этом порядок следования частей не учитывается (в отличие от композиций), то есть разбиения, отличающиеся только порядком частей, считаются равными. В канонической записи разбиения части перечисляются в невозрастающем порядке.

Число разбиений p ( n ) {displaystyle p(n)} натурального числа n {displaystyle n} является одним из фундаментальных объектов изучения в теории чисел.

Примеры

Например, {3, 1, 1} или {3, 2} — разбиения числа 5, поскольку 5 = 3 + 1 + 1 = 3 + 2. Всего существует p ( 5 ) = 7 {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}.

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

Число разбиений

Производящая функция

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

∑ n = 0 ∞ p ( n ) x n = ∏ k = 1 ∞ 1 1 − x k . {displaystyle sum _{n=0}^{infty }p(n)x^{n}=prod _{k=1}^{infty }{frac {1}{1-x^{k}}}.}

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

Пентагональная теорема Эйлера

Изучая производящую функцию последовательности p ( n ) {displaystyle p(n)} , Эйлер сосредоточил внимание на её знаменателе, то есть, на произведении ( 1 − x ) ( 1 − x 2 ) ( 1 − x 3 ) … {displaystyle (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 + … {displaystyle (1-x)(1-x^{2})(1-x^{3})ldots =1-x-x^{2}+x^{5}+x^{7}-x^{12}-x^{15}+x^{22}+x^{26}-x^{35}-x^{40}+ldots }

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

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

∏ k = 1 ∞ ( 1 − x k ) = ∑ q = − ∞ ∞ ( − 1 ) q x ( 3 q 2 − q ) / 2 {displaystyle prod _{k=1}^{infty }left(1-x^{k} ight)=sum _{q=-infty }^{infty }(-1)^{q}x^{(3q^{2}-q)/2}} .

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

Асимптотические формулы

Асимптотическое выражение для количества разбиений было получено Харди и Рамануджаном в 1918 году и независимо от них российским математиком Успенским в 1920 году:

p ( n ) ∼ exp ⁡ ( π 2 3 n − 1 24 ) 4 n 3 {displaystyle p(n)sim {frac {exp left(pi {sqrt {frac {2}{3}}}{sqrt {n-{frac {1}{24}}}} ight)}{4n{sqrt {3}}}}} при n → ∞ {displaystyle n ightarrow infty }

Это выражение даёт, например, p ( 1000 ) ≈ 2 , 44 ⋅ 10 31 {displaystyle p(1000)approx 2{,}44cdot 10^{31}} .

Впоследствии Харди и Рамануджан нашли более точное выражение в виде суммы, и, наконец, Радемахер нашел для асимптотического представления числа разбиений сходящийся ряд.

p ( n ) = 1 π 2 ∑ k = 1 ∞ A k ( n ) k d d n ( sinh ⁡ ( π k 2 3 ( n − 1 24 ) ) n − 1 24 ) , {displaystyle 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}} ight)}} ight)}{sqrt {n-{frac {1}{24}}}}} ight),}

где

A k ( n ) = ∑ 0 ⩽ m < k ( m , k ) = 1 exp ⁡ ( π i s ( m , k ) − 2 π i n m / k ) . {displaystyle A_{k}(n)=sum _{egin{smallmatrix}0leqslant m<k(m,;k)=1end{smallmatrix}}exp left(pi is(m,;k)-2pi inm/k ight).}

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

Рекуррентные формулы

Количество разбиений числа n {displaystyle n} на слагаемые, не превышающие k {displaystyle k} , удовлетворяет рекуррентной формуле:

P ( n , k ) = { P ( n , k − 1 ) + P ( n − k , k ) , k ⩽ n , P ( n , n ) , k > n , {displaystyle P(n,;k)={egin{cases}P(n,;k-1)+P(n-k,;k),&kleqslant n,P(n,;n),&k>n,end{cases}}}

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

P ( 0 , 0 ) = 1 , {displaystyle P(0,;0)=1,} P ( i , 0 ) = 0 {displaystyle P(i,;0)=0} для всех i > 0 {displaystyle i>0}

При этом количество всевозможных разбиений числа n {displaystyle n} равно P ( n , n ) {displaystyle P(n,;n)} .

Диаграммы Юнга

Разбиения удобно представлять в виде наглядных геометрических объектов, называемых диаграммами Юнга, в честь английского математика Альфреда Юнга. Диаграмма Юнга разбиения ( k 1 , k 2 , … , k m ) {displaystyle (k_{1},;k_{2},;ldots ,;k_{m})} — подмножество первого квадранта плоскости, разбитое на ячейки, каждая из которых представляет собой единичный квадрат. Ячейки размещаются в строки, первая строка имеет длину k 1 {displaystyle k_{1}} , над ней расположена строка длиной k 2 {displaystyle k_{2}} , и т. д. до m {displaystyle m} -й строки длины k m {displaystyle k_{m}} . Строки выровнены по левому краю.

Более формально, диаграмма Юнга — это замыкание множества точек ( x , y ) {displaystyle (x,;y)} таких, что

x ,   y > 0 {displaystyle x, y>0} и y < ∑ j = [ x ] m k j , {displaystyle y<sum _{j=[x]}^{m}k_{j},}

где [ x ] {displaystyle [x]} обозначает целую часть x {displaystyle x} .

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

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

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

Применение

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