В задаче номер 4 мы описывали все слова в алфавите {a, b}, разбивающиеся на чередующиеся блоки из букв a и букв b нечётной длины.
Найдите количество таких слов длины 8.
Переборное решение.
Поскольку каждый блок имеет нечётную длину, в слово длины 8 состоит из чётного числа блоков (от 2 до 8). Посчитаем количество способов разбить 8 букв на блоки, а затем умножим это количество на 2, так как каждому разбиению соответствуют два слова, одно из которых начинается на a, а второе на b. Если блоков 8, разбиение на блоки однозначно: в каждом по одной букве. Если блоков 6, то у нас 6 способов выбрать среди них тот, который будет иметь
Если блока 4, то у нас два случая: один блок имеет длину 5, остальные длину 1 (это 4 варианта) или два блока имеют длину 3, а оставшиеся два длину 1 (ещё 6 вариантов).
Наконец, если блоков 2, то всё определяется длиной первого блока, которая может принимать нечётные значения от 1 до 7 (4 варианта). Итоговый ответ
Рекуррентное решение.
Заметим, что количество слов длины n, начинающихся с а и с b совпадают. Обозначим это количество за Слово, начинающееся с буквы a может начинаться с ab, если вторая буква b, таких слов Если же вторая буква a, то и третья тоже a. Отделим первые две буквы, и у нас получится слово из букв, начинающееся на a. Таких слов Получаем рекуррентную формулу то есть формулу для чисел Фибоначчи. Значит, ответ это удвоенное число Фибоначчи с соответствующим номером, т. е.
Ответ: 42.