Question

Рассмотрим алфавит из 2 букв. Словом будем считать любое конечное сочетание букв. Назовём слово непроизносимым, если в нём встречается больше двух одинаковых букв подряд. Сколько всего существует непроизносимых слов из 7 букв?

Answer 1

Ответ: 86

Решение:

Всего есть $2^7=128$ слов из 7 букв, каждую из которых можно выбрать из двух вариантов. Посчитаем, сколько из этих слов произносимые.

Введём a и b - количество произносимых слов, оканчивающихся не на две одинаковые буквы и на две одинаковые буквы. Будем вычислять a и b для каждой длины слова n. Общее количество произносимых слов будет вычисляться по формуле a + b.

Для n = 1, очевидно, a = 2, b = 0. Значения для следующих n можно получить из предыдущих: новое a будет равно сумме предыдущих a и b (можно получить произносимое слово из любого слова с меньшей длиной путем приписывания в конец буквы, которая будет отлична от последней); новое b будет равно предыдущему a (на пару одинаковых букв будут оканчиваться только те слова, у которых на прошлом шаге буквы были разные - иначе в конце появятся как минимум 3 одинаковые буквы).

Заполненная таблица имеет вид:

$\begin{array}{c|c|c|c}n & a & b & a + b\\1 & 2 & 0 & 2\\2 & 2 & 2 & 4\\3 & 4 & 2 & 6\\4 & 6 & 4 & 10\\5 & 10 & 6 & 16\\6 & 16 & 10 & 26\\7 & 26 & 16 & 42\end{array}$

Итак, произносимых слов длины 7 всего 42, тогда непроизносимых - $128-42=86$.

(Кстати, в последовательности количества произносимых слов можно заметить удвоенную последовательность Фибоначчи - последовательности, начинающейся с 0 и 1, в которой каждый новый член равен сумме двух предыдущих)