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

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

n = a₁ + a₂ +    + a_k , k>0, a₁ a₂     a_k > 0.

Пусть 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 справа показана сопряженная диаграмма Ферреса. Она будет соответствовать разбиению 5=3 + 2.

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