Число двоичных слов длины n без двух соседних нулей подчиняется соотношению xn=xn−1+xn−2: слово начинается либо с единицы (дальше любое подходящее слово длины n−1), либо с «01» (дальше любое подходящее слово длины n−2). Получаются числа 2,3,5,8,13,… — это числа Фибоначчи 1,1,2,3,5,8,13,…, только с другой нумерацией, а характеристическое уравнение λ2−λ−1=0 даёт для них явную формулу и отношение соседних чисел, стремящееся к 21+5.
Что пригодится из прошлого:два вещественных корня — формула (5) для xn=pxn−1+qxn−2; двоичные коды — слова из нулей и единиц; правило суммы. Если эти главы знакомы, читайте дальше. Если нет — загляните по ссылке, потом возвращайтесь.
Задача
Задача. Найти число слов длины n в алфавите {0,1}, которые не содержат двух соседних нулей.
Обозначим это число xn. Выпишем малые случаи:
n=1: слова 0 и 1 — оба подходят, x1=2;
n=2: из четырёх слов 00,01,10,11 не подходит только 00: x2=3;
n=3: слова 010, 011, 101, 110, 111 — x3=5 (из восьми слов не подходят три: 000, 001 и 100).
Для n=4 подходящих слов 8: 0101, 0110, 0111, 1010, 1011, 1101, 1110, 1111.
Рекуррентное соотношение
Пусть n≥3. Разобьём все подходящие слова длины n на два непересекающихся класса по первой букве.
а) Слова, начинающиеся с «1». После единицы идёт любое подходящее слово длины n−1: единица в начале не может создать пару нулей. Таких слов xn−1.
б) Слова, начинающиеся с «0». Вторая буква обязательно «1» (иначе получилось бы «00»). После «01» идёт любое подходящее слово длины n−2: единица на второй позиции отделяет начальный нуль от остального слова, поэтому пара нулей не может возникнуть на границе, а хвост нужно проверять сам по себе. Таких слов xn−2.
По правилу суммы
xn=xn−1+xn−2,x1=2,x2=3.
Первые значения: 2,3,5,8,13,21,… — каждое следующее равно сумме двух предыдущих.
Формула (5) из предыдущей главы ждёт значения x0 и x1. У нас заданы x1=2, x2=3; так как x2=x1+x0, достаточно положить x0=1 (3=2+1): слово длины 0 — «пустое», без символов, и оно одно. Тогда соотношение xn=xn−1+xn−2 верно при всех n≥2, формула (5) применима, и a=1, b=2:
Цель — записать c1 и c2 как степени корней: тогда итоговая формула получится короче. Корни удовлетворяют λ2=λ+1, поэтому λ22=λ2+1=23+5 и λ12=λ1+1=23−5. Тогда 2−λ1=2−21−5=23+5=λ22, а λ2−2=21+5−2=25−3=−23−5=−λ12. Значит, c2=5λ22, c1=−5λ12, и
Сравнив, видим Fn=xn−1 при n≥1, поэтому (заменяем n на n−1 в формуле для xn)
Fn=51(21+5)n+1−(21−5)n+1.
Эта последовательность называется последовательностью Фибоначчи, а формула — формулой Бине. В других книгах нумерацию часто сдвигают: F0=0, F1=1. Поэтому смотрите на начальные значения.
Проверка.n=0: 5λ2−λ1=55=1 ✓. n=1: 5λ22−λ12=5(λ2−λ1)(λ2+λ1)=1⋅1=1 ✓ (так как λ1+λ2=1).
Два свойства чисел Фибоначчи
1. Соседние числа взаимно просты:(Fn,Fn+1)=1 (наибольший общий делитель равен единице). Доказательство по алгоритму Евклида: любой общий делитель Fn+1 и Fn делит и Fn+1−Fn=Fn−1, то есть является общим делителем Fn и Fn−1. Обратно, общий делитель Fn и Fn−1 делит Fn+1=Fn+Fn−1. Значит, наборы общих делителей совпадают и НОД(Fn+1,Fn)=НОД(Fn,Fn−1). Повторяя, дойдём до НОД(F1,F0)=НОД(1,1)=1.
2. Отношение соседних чисел приближается к числу 21+5 — «золотому сечению»: чем больше n, тем ближе оно к этому числу (это записывают через предел — число, к которому значения приближаются сколь угодно близко при больших n):
n→∞limFnFn+1=21+5≈1,618.
Объяснение по формуле Бине: FnFn+1=λ2n+1−λ1n+1λ2n+2−λ1n+2=λ2⋅1−(λ1/λ2)n+11−(λ1/λ2)n+2. Так как λ2λ1=5+15−1<1, степени (λ1/λ2)n приближаются к нулю (число, меньшее 1 по модулю, при возведении во всё большую степень становится всё меньше), дробь приближается к 1, и всё выражение — к λ2.
В последнем столбце — отличие дроби FnFn+1 от 21+5:
n
Fn
Fn+1/Fn
Отличие
1
1
2,0000
0,3820
2
2
1,5000
0,1180
3
3
1,6667
0,0486
4
5
1,6000
0,0180
5
8
1,6250
0,0070
6
13
1,6154
0,0026
7
21
1,6190
0,0010
8
34
1,6176
0,0004
9
55
1,6182
0,0001
10
89
1,6180
0,0001
Та же последовательность в другой задаче
Лесенка из n ступенек; за один шаг поднимаются на одну или две ступеньки. Сколькими способами можно подняться? Обозначим cn. Первый шаг — на одну ступеньку (дальше cn−1 способов) либо на две (cn−2): cn=cn−1+cn−2, c0=c1=1 (подняться на 0 ступенек можно одним способом — ничего не делать; на одну ступеньку — тоже одним). Это в точности Fn.
Частые ошибки
Спутать нумерацию. В этой главе F0=F1=1; при F0=0 номера сдвинуты на единицу.
Решать соотношение, не проверив начальные условия. Формула (5) требует x0 и x1; при заданных x1,x2 сначала восстановите x0 (здесь x0=1).
Считать число слов 2n. Запрет «00» сильно сокращает: для n=10 подходит всего F11=144 слов из 1024.
Ожидать, что формула Бине даёт дробные значения. Иррациональные слагаемые взаимно сокращаются — получаются целые числа.
Проверь себя
1. Сколько существует двоичных слов длины 6 без двух соседних нулей?
Решение
x6=x5+x4=13+8=21 (последовательность 2,3,5,8,13,21). Это F7=21.
2. Вычислите F10.
Решение
1,1,2,3,5,8,13,21,34,55,89: F10=89.
3. Вычислите F9F10 и сравните с 21+5.
Решение
5589=1,61818, а 21+5=1,61803… Различие уже в четвёртом знаке после запятой.
4. Сколькими способами можно подняться по лесенке из 7 ступенек шагами по 1 или 2 ступеньки?
Решение
c7=F7=21.
Итог
Слова без «00»: xn=xn−1+xn−2, x1=2, x2=3; начинаются либо с «1», либо с «01».