Математика — слова длины 13 из ТБАНК с Т среди двух соседних

Условие

Пусть b_n — количество слов длины n из букв {Т, Б, А, Н, К} таких, что среди любых двух последовательных букв хотя бы одна — это Т.

Найдите b_13.

Решение

Подход — рекуррентное соотношение

Пусть a_n — число слов длины n, удовлетворяющих условию и заканчивающихся на Т. Пусть c_n — число таких слов, заканчивающихся на не-Т (любую из 4 букв Б, А, Н, К).

Тогда b_n = a_n + c_n.

Переходы:

• Слово длины n, заканчивающееся на Т: после Т можно поставить любую из 5 букв. То есть в слове длины n+1 слово, заканчивающееся на любую букву, может пойти после слова длины n с Т на конце:

  a_{n+1} = a_n + c_n   (после любого окончания добавили Т)
  c_{n+1} = 4 * a_n     (после Т добавили одну из 4 не-Т; после не-Т добавлять не-Т НЕЛЬЗЯ — нарушится условие)
  

• Если слово на не-Т заканчивается, следующая буква должна быть Т (иначе получится «не-Т, не-Т» — нарушение).

Уточнение

• a_{n+1} = добавляем Т: можно к любому слову длины n → a_{n+1} = b_n = a_n + c_n.
• c_{n+1} = добавляем не-Т: можно только к слову, заканчивающемуся на Т (иначе будет «не-Т, не-Т»). Не-Т букв 4 → c_{n+1} = 4 * a_n.

Базовые случаи

n = 1: одно слово из одной буквы. Условие про «две последовательных» вакуумно истинно.

• a_1 = 1 (буква Т)
• c_1 = 4 (Б, А, Н, К)
• b_1 = 5

Вычисление до n = 13

Реализация

a, c = 1, 4
for _ in range(12):
    a, c = a + c, 4 * a
b13 = a + c
print(b13)  # 325525

Сложность

O(n) времени, O(1) памяти.

Подводные камни

1. Считать, что «хотя бы одна Т» = «обязательно одна Т». Это «не более одной не-Т подряд». Соседство ББ запрещено, ТТ — разрешено.
2. Случай n = 1. Там нет двух соседних букв, поэтому ограничение не действует — все 5 слов. Часто упускают.
3. Подсчёт «по дополнению». Можно считать 5^n − плохие. Но «плохое» = слово с двумя не-Т подряд — там тоже включения-исключения и в итоге сложнее.

Эталонный ответ

b_13 = 325 525.