9. Рекуррентные соотношения. Числа Фибоначчи. Решение рекуррентного соотношения второго порядка.

Рекуррентные соотношения позволяют свести решение некоторой комбинаторной задачи с n элементами к решению аналогичной задачи с n­-i элементами, где i<n.

В ряде случаев рекуррентные соотношения используются для задания функций натурального аргумента; так, например, определяются числа Фибоначчи, F(n), характеризуемые условиями: F(n + 1)=F(n)+F(n-1), F(0)=1, F(1)=2.(2)

С помощью этой формулы F(n) могут быть найдены для достаточно больших n: F(2)=3, F(3)=5, F(4)=8, F(5)=13, F(6)=21, F(7)=34 ... Порядком рекуррентного соотношения называется натуральное число k_, позволяющее определить f(n+k) через f(n+i), где i = 0,1,..., k-1. Очевидно, числа Фибоначчи задаются рекуррентным соотношением 2-го порядка.

Рекуррентному соотношению может удовлетворять бесконечное число последовательностей. Это связано с тем, что, если оно имеет порядок k, то первые k значений последовательности оказываются неопределенными. Следовательно, каждое из них может быть задано бесчисленным количеством способов, что и определяет бесконечное число последовательностей, удовлетворяющих заданной рекуррентной формуле. Таким образом, при использовании рекуррентных соотношений необходимо учитывать следующее

Определение 4. Решением рекуррентного соотношения называется всякая последовательность, подстановка любых членов которой в определяющее его равенство обращает это равенство в тождество.

Для нахождения однозначного решения рекуррентного соотношения необходимо задавать начальные условия, число которых должно совпадать с его порядком.

Например, при определении чисел Фибоначчи в (2), кроме рекуррентной формулы второго порядка, имеется два начальных значения F(n):F(0)=1 и F(1)=2. Именно эти начальные условия позволяют найти нужную числовую последовательность. Достаточно изменить F(0) и F(1), чтобы вместо чисел Фибоначчи рекуррентная формула (1) определила другой набор чисел. Так, при F(0)=1 и F(l)=3 мы имеем F(2)=4, F(3)=7, F(4)=11, F(5)=18, F(6)=29, F(7)=47, ..., что явно не совпадает с приведенными выше соответствующими значениями чисел Фибоначчи.

Общих правил нахождения решений рекуррентных соотношений не существует. Однако имеются способы решения линейных соотношений с постоянными коэффициентами, которые записываются в виде (3) где а_i не зависят от n и k. Эти способы очень сильно напоминают методы решения линейных обыкновенных дифференциальных уравнений k-го порядка с постоянными коэффициентами.

9. Рекуррентные соотношения. Числа Фибоначчи. Решение рекуррентного соотношения второго порядка.

Сначала определим класс рекурсивных функций, известный как класс линейных рекурсивных функций.

ОПРЕДЕЛЕНИЕ 11.1. Рекурсивное отношение вида называется линейным рекуррентным отношением порядка р.

ОПРЕДЕЛЕНИЕ 11.2. Линейное рекуррентное отношение вида называется линейным однородным рекуррентным отношением порядка р.

Рассматриваемое отношение названо линейным рекуррентным отношением, поскольку показатель степени каждого а_i равен единице. Другими словами, ни одно из а_i не возводится в какую-либо степень, кроме первой. Таким образом, отношение не будет линейным, т.к. a_n-1 возведено в третью степень. Однако, отношение а_n=3n³a_n-1+na_n-2 линейно. К сожалению, рассматриваемое множество линейных рекуррентных отношений необходимо ограничить еще в большей степени. Дополнительно требуется, чтобы коэффициенты c_i(n) для каждого i были константами.

ОПРЕДЕЛЕНИЕ 11.3. Линейное рекурсивное отношение вида , с постоянными коэффициентами с_i при называется линейным рекуррентным отношением с постоянными коэффициентами порядка р.

Далее будем рассматривать некоторые линейные рекурсии такого вида, но даже при указанных выше ограничениях возможности решения задачи будут зависеть от выбора функции f(n). Линейные рекуррентные отношения с постоянными коэффициентами общего вида рассматриваются в следующем разделе. Но прежде, чем решать задачи такого типа, требуется ввести еще одно ограничение на рассматриваемый класс линейных рекурсий.

ОПРЕДЕЛЕНИЕ 11.4. Линейное рекуррентное отношение вида ,

с постоянными коэффициентами с; при называется линейным однородным рекуррентным отношением с постоянными коэффициентами порядка р.

Такое отношение является частным случаем линейного рекуррентного отношения с постоянными коэффициентами, когда f(n)=0. Один из известных примеров — последовательность Фибоначчи: 1,1,2,3,5,8,13,21,..., в которой каждый элемент после первых двух равен сумме двух предшествующих элементов последовательности. Рекурсивно это условие определено следующим образом. Фиб(1) = 1; Фиб(2) = 1; Фиб(n) = Фиб(n - 1) + Фиб(n - 2) для n > 2.

Таким образом, в этом случае р=2, c₁=1 и с₂=1

ТЕОРЕМА 11.12. Пусть рекуррентное отношение а_n = c₁a_n-1 + с₂а_n-2 + с₃а_n-3 + …+ c_pa_n-p имеет характеристическое уравнение rⁿ – c₁r^n-1 – с₂r^n-2 – с₃r^n-3– … – c_рr^n-p = 0.Если r_i — корень характеристического уравнения кратности q_i, так что является множителем характеристического многочлена, то

включается в общее решение для а_n.

10. Числа Каталана.

Числа Катала́на — числовая последовательность, встречающаяся во многих задачах комбинаторики. Последовательность названа в честь бельгийского математика Каталана, хотя была известна ещё Л. Эйлеру.

Первые несколько чисел Каталана:

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862

Определения

n-е число Каталана   можно определить одним из следующих способов:

Количество разбиений выпуклого (n+2)-угольника на треугольники непересекающимися диагоналями.

Количество правильных скобочных последовательностей длины 2n, то есть таких последовательностей из n левых и n правых скобок, в которых количество открывающих скобок равно количеству закрывающих, и в любом её префиксе открывающих скобок не меньше, чем закрывающих.

Например, для n=3 существует 5 таких последовательностей:

((())), ()(()), ()()(), (())(), (()())

то есть  .

Количество способов соединения 2n точек на окружности n непересекающимися хордами.

Количество неизоморфных упорядоченных бинарных деревьев с корнем и n+1 листьями.

Свойства

Числа Каталана удовлетворяют рекуррентному соотношению:

 и   для 

Это соотношение легко получается из того, что любая непустая правильная скобочная последовательность однозначно представима в виде w=(w1)w2, где w1, w2 — правильные скобочные последовательности.

Производящая функция чисел Каталана равна:

Числа Каталана можно выразить через биномиальные коэффициенты:

Другими словами, число Каталана   равно разности центрального биномиального коэффициента и соседнего с ним в той же строке треугольника Паскаля.

Асимптотически