На доске написано 20 -буквенное слово, состоящее только из букв А и В. Назовем крутизной слова количество способов стереть некоторые его буквы так, чтобы на доске остались четыре буквы, образующих комбинацию ABBA . Например, слово ABBAAB имеет крутизну 2

Решение задачи о наибольшей возможной крутизне слова

1. Дано

• Длина слова $L = 20$ букв.
• Слово состоит только из букв А и В.
• Требуемая комбинация (подпоследовательность) — ABBA.
• Крутизна слова — количество способов получить подпоследовательность ABBA, стирая лишние буквы.

2. Найти

Наибольшую возможную крутизну слова длины 20.

3. Решение

Пусть наше слово $S$ имеет длину $L=20$. Мы ищем количество способов выбрать четыре индекса $i_1, i_2, i_3, i_4$ такие, что $1 \le i_1 < i_2 < i_3 < i_4 \le 20$, и буквы в этих позициях образуют последовательность ABBA: