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



             

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


А еще через месяц приплод дадут и исходная пара кроликов, и пара кроликов, появившаяся два месяца тому назад. Поэтому всего будет 5 пар кроликов. Обозначим через
F(n)

количество пар кроликов по истечении

n
месяцев с начала года. Ясно, что через
n + 1

месяцев будут эти

F(n)
пар и еще столько новорожденных пар кроликов, сколько было в конце месяца
n - 1
, то есть еще
F(n - 1)
пар кроликов. Иными словами, имеет место рекуррентное соотношение
F(n + 1) = F(n) + F(n - 1)

(7.2)

Так как, по условию,

F(0) = 1
и
F(1) = 2
, то последовательно находим
F(2)=3,F(3)=5,F(4)=8
и т.д.

В частности,

F(12) = 377
.

Числа

F(n)
называются числами Фибоначчи. Они обладают целым рядом замечательных свойств. Теперь выведем выражение этих чисел через
C_m^k
. Для этого установим связь между числами Фибоначчи и следующей комбинаторной задачей.

Найти число

n
последовательностей,состоящих из нулей и единиц, в которых никакие две единицы не идут подряд.

Чтобы установить эту связь, возьмем любую такую последовательность и сопоставим ей пару кроликов по следующему правилу: единицам соответствуют месяцы появления на свет одной из пар "предков" данной пары (включая и исходную), а нулями - все остальные месяцы. Например, последовательность 010010100010 устанавливает такую "генеалогию": сама пара появилась в конце 11-го месяца, ее родители - в конце 7-го месяца, "дед" - в конце 5-го месяца и "прадед" - в конце второго месяца. Исходная пара кроликов тогда зашифровывается последовательностью 000000000000.

Ясно, что при этом ни в одной последовательности не могут стоять две единицы подряд - только что появившаяся пара не может, по условию, принести приплод через месяц. Кроме того, при указанном правиле различным последовательностям отвечают различные пары кроликов, и обратно, две различные пары кроликов всегда имеют разную "генеалогию", так как, по условию, крольчиха дает приплод, состоящий только из одной пары кроликов.

Установленная связь показывает, что число

n
-последовательностей, обладающих указанным свойством, равно
F(n)
.

Докажем теперь, что

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

(7.3)

где

p = \frac{{n + 1}} {2}
, если
n
нечетно, и
p = \frac{n} {2}
, если
n
четно.


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