Условие
Найдите количество слов длины 10, состоящих только из букв
"а" и "б" и не содержащих в записи двух букв "б" подряд.
Подсказка
Обозначьте за a
n
количество слов длины n, состоящих только из букв
"а" и "б" и не содержащих в записи двух букв "б" подряд.
В последовательности
a
1, a
2, ..., a
n выразите
каждый следующий член через предыдущие.
Решение
Обозначим за a
n
количество слов длины n, состоящих только из букв
"а" и "б" и не содержащих в записи двух букв "б" подряд.
Таким образом, находим
a
1=2, a
2=3.
Покажем, что a
n можно выразить через
a
n-1 и a
n-2.
Количество слов длины n,
не содержащих в записи двух букв "б" подряд и начинающихся с
буквы "а", равно a
n-1, так как
после первой буквы может следовать любое слово длины n-1,
не содержащее двух "б" подряд.
Пусть слово длины n начинается с буквы "б".
Если в этом слове нет двух "б" подряд, то вторая буква - "а",
а далее может следовать любое слово длины n-2,
не содержащее двух "б" подряд.
Таким образом,
количество слов длины n,
не содержащих в записи двух букв "б" подряд и начинающихся с
буквы "б", равно a
n-2.
Тем самым, мы показали, что
a
n=a
n-1+a
n-2.
Теперь последовательно вычисляем
a
3=a
2+a
1=3+2=5,
a
4=a
3+a
2=5+3=8 и т.д.,
a
10=a
9+a
8=144.
Заметим, что получающиеся числа a
n - это хорошо
известные числа Фибоначчи.
Ответ
144
Источники и прецеденты использования