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

         

Другой метод доказательства


В предыдущем разделе непосредственно установлена связь между задачей Фибоначчи и комбинаторной задачей. Эту связь можно установить и иначе, непосредственно доказав, что число

решений комбинаторной задачи удовлетворяет тому же рекуррентному соотношению

(7.5)

что и числа Фибоначчи. В самом деле, возьмем любую

-последовательность нулей и единиц, удовлетворяющую условию, что никакие две единицы не идут подряд. Она может оканчиваться или на 0, или на 1. Если она оканчивается на 0, то, отбросив его, получим
-последовательность, удовлетворяющую нашему условию. Если взять любую
- последовательность нулей и единиц, в которой подряд не идут две единицы, и приписать к ней нуль, то получим
-последовательность с тем же свойством. Таким образом доказано, что число последовательностей, оканчивающихся на нуль, равно
.

Пусть теперь последовательность оканчивается на 1. Так как двух единиц подряд быть не может, то перед этой единицей стоит нуль. Иными словами, последовательность оканчивается на 01. Остающаяся же после отбрасывания 0 и 1

-последовательность может быть любой, лишь бы в ней не шли подряд две единицы. Поэтому число последовательностей, оканчивающихся единицей, равно
. Но каждая последовательность оканчивается или на 0, или на 1. В силу правила суммы получаем, что
.

Таким образом, получено то же самое рекуррентное соотношение. Отсюда еще не вытекает, что числа

и
совпадают.



Содержание раздела