Комбинаторные алгоритмы для программистов



             

Рекуррентные соотношения - часть 3


Иными словами,
p
- целая часть числа
\frac{{n + 1}} {2}
(в дальнейшем будем обозначать целую часть числа
\alpha
через
E(\alpha )
; таким образом,
p = E(\frac{{n + 1}} {2})
).

В самом деле,

F(n)
- это число всех
n
- последовательностей из 0 и 1, в которых никакие две единицы не стоят рядом. Число же таких последовательностей, в которые входит ровно
k
единиц и
n - k
нулей, равно
C_{n - k + 1}^k
. Так как при этом должно выполняться неравенство
k \leqslant n - k + 1
, то
k
изменяется от 0 до
E(\frac{{n + 1}}{2})
. Применяя правило суммы, приходим к соотношению (7.3).

Равенство (7.3) можно доказать и иначе. Положим

G(n)=C_{n+1}^0+C_n^1+C_{n-1}^2+\ldots+C_{n-p+1}^p,\vspace{-1mm}

где

p = \frac{{n + 1}}{2}
. Из равенства
C_n^k=C_{n-1}^k+C_{n-1}^{k-1}

легко следует, что

G(n)=G(n-1)+G(n-2).

(7.4)

Кроме того, ясно, что

G(1)=2=F(1)
и
G(2)=3=F(2)
. Так как обе последовательности
F(n)
и
G(n)

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

X(n)=X(n-1)+X(n-2)
, то имеем
G(3)=G(2)+G(1)=F(2)+F(1)=F(3),

и, вообще,

G(n) = F(n)
.




Содержание  Назад  Вперед