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

Разбиением натурального числа n на k слагаемых называется класс эквивалентности последовательностей таких положительных натуральных чисел (b₁, b₂, × × ×, b_k), что

n = b₁ + b₂ + × × × + b_k, k>0, b₁, b₂, × × ×, b_k > 0.

Две последовательности считаются эквивалентными, если они отличаются перестановкой элементов b_i. Каждый класс эквивалентности можно представить единственным образом как такую невозрастающую последовательность

a₁ ³ a₂ ³ × × × ³ a_k,

что a₁+ a₂, + × × × + a_k = n. Пусть P(n,k) – число разбиений n на k слагаемых. Тогда число всех разбиений равно , n>0.

Полагаем по определению P(0)=P(0,0)=1.

Пример 1. P(5)=7:

5 = 5,

5 = 4+1,

5 = 3+2,

5 = 3+1+1,

5 = 2+2+1,

5 = 2+1+1+1,

5 = 1+1+1+1+1.

Диаграмма Ферреса для n = a₁ + a₂ + × × × + a_k состоит из k строк, в i -строке содержащих a_i точек. Например для Например, для 5 = 2 + 2 + 1 диаграмма Ферреса показана на рисунке 3.1. На этом рисунке показана также сопряженная диаграмма Ферреса.

Рис. 3.1. Диаграммы Ферреса

Лемма 1. Число разбиений P(n) равно количеству решений

(l₁, l₂, × × ×, l_n)

уравнения l₁ ×1 + l₂ ×2 + × × ×+ l_n ×n = n.

Доказательство. Если среди чисел a₁³ a₂ ³ × × × ³ a_k разбиения числа n имеется l₁ - единиц, l₂ - двоек, × × ×, l_n - n -ок, то получаем решение уравнения. Ясно, что это соответствие взаимно однозначно.

Обозначим через P_h(n) количество разбиений числа n на слагаемые, не большие чем h.

Теорема 1. Производящая функция последовательности чисел разбиений P_h(0), P_h (1), P_h (2), × × × равна .

Доказательство. Произведение равно

(1+x+x²+× × ×)(1+x²+x⁴+× × ×)(1+ x³+ x⁶+ × × ×)× × ×(1+ x^h + x^2h + × × ×)

Если перемножить содержимое скобок, то получим многочлен, равный умме

. Отсюда коэффициент при xⁿ равен числу последовательностей (l₁, l₂, × × ×, l_h),

для которых l₁ ×1 + l₂ ×2 + × × ×+ l_h ×h = n. Он будет равен числу разбиений n на слагаемые, не большие чем h.

Следствие 1. Производящая функция последовательности чисел разбиений P(0), P(1), P(2), × × × равна .