Формулировка задачи (коротко): посчитать количество слов длины $n$ над алфавитом размера $k$, такие, что
- нет двух одинаковых подрядных букв (то есть для всех $i$ $x_i\ne x_{i+1}$);
- нет подстроки длины $3$, все буквы которой различны (то есть запрещены троики $x_i,x_{i+1},x_{i+2}$ с тремя разными символами).
Ключевое наблюдение (значит упрощение задачи): если одновременно $x_i\ne x_{i+1}$ и троика $x_i,x_{i+1},x_{i+2}$ не содержит трёх различных, то при $x_i\ne x_{i+1}$ и $x_{i+1}\ne x_{i+2}$ остаётся только вариант $x_i=x_{i+2}$. Значит для всех $i$ выполняется
$$x_i=x_{i+2},$$ то есть слово периодично с периодом $2$ (через одно символы равны). В сочетании с запретом одинаковых соседей это даёт: слово — чередование двух разных букв $A$ и $B$ (шаблон $ABAB\dots$, с $A\ne B$). Отсюда очевиден итоговый счёт:
$$a_1=k,a_n=k(k-1)\text{для}n\ge 2.$$ (Особые случаи: при $k=1$ получаем $a_1=1$, для $n\ge 2$ — $0$.)
Дальше — способы решения и обсуждение.
1) Рекуррентные соотношения
- Постановка: пусть $a_n$ — искомое число слов длины $n$. Для $n\ge 3$ рассмотрим последние два символа $(x_{n-1},x_n)$. Они различны, всего таких пар $k(k-1)$. Для заданной такой пары возможное добавление символа $x_{n+1}$ должно удовлетворять $x_n\ne x_{n+1}$ и запрещению троики — следовательно единственный допустимый выбор $x_{n+1}=x_{n-1}$. Значит из любой допустимой длины $n\ge 2$ есть ровно один допустимый переход к длине $n+1$.
- Следствие: $a_2=k(k-1)$ и для всех $n\ge 2$ $a_{n+1}=a_n$, т.е.
$$a_n=k(k-1)(n\ge 2).$$ Преимущества: простой, детерминированный вывод, малые вычисления. Ограничения: требует интуиции о состоянии «последние две буквы» и справедлив только потому, что правило локальное и сильно ограничивает расширения; при более сложных локальных шаблонах рекурренты могут быть значительно более сложными.
2) Метод автомата (ДКА / матрицы переходов)
- Постройте автомат, состояния которого — упорядоченные пары различных букв $(u,v)$ (последние два символа); начальные состояния для длины $1$ можно трактовать отдельно. Переход из состояния $(u,v)$ ведёт единственно в состояние $(v,u)$ (потому что следующий символ обязателен $u$). Матрица переходов — пермутационная матрица с собственной структурой: каждая соответствующая вершина имеет ровно один выход.
- Количество допустимых слов длины $n$ — число путей длины $n-2$ в этом автомате, умноженное на число допустимых первых двух символов $k(k-1)$ (или отдельно учитывать $n=1$). Из структуры матрицы видно, что число путей не меняется с увеличением длины: даёт тот же результат
$$a_1=k,a_n=k(k-1)(n\ge 2).$$ Преимущества: автоматический, системный, даёт явную матричную интерпретацию; легко обобщается на другие локальные ограничения с конечным числом состояний. Ограничения: число состояний может быть $O(k^m)$ при учёте последних $m$ символов, что даёт экспоненциальный рост сложности в общем случае.
3) Метод включения–исключения (и метод кластеров / Goulden–Jackson)
- Можно начать с подсчёта слов без равных соседей: $k(k-1{)}^{n-1}$, затем исключать те, что содержат запрещённые троики (в каждой позиции i событие «тройка i — три разные»). Однако эти события перекрываются и имеют сложную зависимость. Прямой IE даёт громоздкие суммы; полезен подход кластеров (Goulden–Jackson), который строит автоморфизмы запрещённых кластеров и даёт формулу через рациональные функции. В нашем конкретном случае анализ кластеров показывает, что единственные бесклассные слова без соседних равных и без запрещённых троек — те, у которых для каждого i $x_i=x_{i+2}$ (т.е. чередование), что снова даёт
$$a_n=k(k-1)(n\ge 2).$$ Преимущества: общий метод, применим к произвольному набору запрещённых подслов; даёт точные формулы даже при перекрытиях. Ограничения: часто приводит к сложной комбинаторике кластеров и вычислительно трудоёмок — в простых случаях (как здесь) чрезмерен; для многих запретов аналитика и вычисления становятся громоздкими.
Краткое заключение: из локальных ограничений следует строгая периодичность через два символа, поэтому ответ прост: $a_1=k$, $a_n=k(k-1)$ для $n\ge 2$. Рекуррентный и автоматный подходы дают короткое и прозрачное решение; включение–исключение универсально, но в этом случае избыточно и сложнее в реализации.