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

Рекуррентные соотношения - часть 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)$

.

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