3.2. Разбиения чисел
Разбиениемнатурального числаnнаkслагаемых называется последовательность таких положительных натуральных чисел( a1, a2, , ak ), что
n = a1 + a2 + + ak , k>0, a1 a2 ak > 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 = a1 + a2 + + akсостоит изkстрок, аi-строка содержитaiточек. Например, для 5 = 2 + 2 + 1 диаграмма Ферреса показана слева на рисунке 3.1. Если отразить диаграмму относительно ее главной диагонали, то мы получим диаграмму Ферреса, которая называется сопряженной. На рисунке 3.1 справа показана сопряженная диаграмма Ферреса. Она будет соответствовать разбиению 5=3 + 2.
|
|
|
Рис. 3.1. Диаграммы Ферреса
Лемма 1. Число разбиений p(n) равно количеству решений
(1 , 2 , , n )
уравнения 1 1 + 2 2 + + n n = n .
Доказательство.Если среди чиселa1 a2 ak разбиения числаnимеется1единиц ,2 двоек ,,n n-ок , то получаем решение уравнения. Ясно, что это соответствие взаимно однозначно.
Обозначим через Ph(n)количество разбиений числаnна слагаемые, не большие чемh.
Теорема 1. Производящая функция последовательности чисел разбиений
Ph(0),
Ph
(1), Ph
(2),
равна
.
Доказательство.Произведение равно
(1+x+x2+ )(1+x2+x4+ )(1+ x3+ x6+ ) (1+ xh + x2h + ).
Если перемножить
содержимое скобок, то получим многочлен,
равный сумме одночленов
.
Отсюда коэффициент приxnравен числу последовательностей (1,2,,h), для которых11 +22 ++hh=n. Он будет равен
числу разбиенийnна
слагаемые, не большие чемh.
Следствие 1. Производящая функция последовательности чисел разбиений
P(0),
P(1),
P(2),
равна
.
3.3. Числа Фибоначчи
Вычислим производящую функцию F(x) чисел Фибоначчи
F0 = F1 = 1,Fn+1 = Fn + Fn-1 приn 1.
Т.о. числа Фибоначчи– это последовательность чисел1, 1, 2, 3, 5... Имеют место соотношения:
.
Приходим к уравнению
F(x)=1
+ x + x2
+ x(F(x)-1)для
.
Решая это уравнение, получаем
, для некоторыхA,B,
при
,
.
Отсюда мы видим, что рядF(x)равен сумме геометрических прогрессий.
Находим
,
. Следовательно,
.
Отсюда получаем формулу для вычисленияk–го числа Фибоначчи,
,
для всехk = 0, 1, 2,
∙ ∙ ∙ .
3.4. Рекуррентные уравнения
Рассмотрим обобщение последовательностей Фибоначчи. Формула
un + r = c1 un + r – 1 + c2 un + r – 2 + ∙ ∙ ∙ + cr un
называется однородным линейным рекуррентным уравнением порядка r. Ее решением является последовательность{un}, однозначно определенная начальными значениямиu0, u1, u2, ∙ ∙ ∙ , ur –1 . Решение такого уравнения называетсявозвратнойилирекуррентнойпоследовательностью порядка r.
Пример 1. Геометрическая прогрессия является решением уравнения un+1=qun . Ее члены описываются формулой un= u0qn . Отсюда геометрическая прогрессия является возвратной последовательностью порядка 1.
Пример 2. Арифметическая прогрессия un = u0 + nd удовлетворяет соотношению un+1 un = un+2 un+1 . Получаем однородное рекуррентное уравнение un+2 = 2un+1 un . Начальные данные задаются значениями u0 и u1=u0+d. Отсюда арифметическая прогрессия является возвратной последовательностью порядка 2.
Пример 3.Произвольная периодическая последовательность является возвратной последовательностью порядкаp, удовлетворяющей рекуррентному соотношению
un + p=un. Здесьp– период последовательности.
Для заданного рекуррентного уравнения
un + r = c1 un + r – 1 + c2 un + r – 2 + ∙ ∙ ∙ + cr un
найдем производящую
функцию
возвратной последовательности {un}. ОбозначимK(x)=1
c1x
c2x2
∙
∙ ∙
crxr.
Теорема 1. Произведение u(x)K(x) = D(x) является многочленом степени меньшей, чем r.
Доказательство.Вычислим коэффициент рядаD(x)приxn+ r . Он при n≥ 0 будет равенun + r (c1 un + r – 1 + c2 un + r – 2 + ∙ ∙ ∙ + cr un)= 0. ОтсюдаD(x)– многочлен степени меньшей, чем n.