Найти количество кортежей 0, 1, 2

[AVV]

Или, хотя бы, рекуррентное соотношение для количества кортежей $0, 1, 2$ данной длины таких, что соседние числа отличаются не более чем на $1$. То есть, например, $122$ - правильный кортеж, а $1201$ - неправильный.

Число "правильных" длины $n$ есть $3^n - \text{\{число .
А, кажется, посчитать "неправильные" кортежи проще. Но что-то не выходит. Ясно, что "неправильный" кортеж длины $n+1$ содержит "неправильный" длины $n$ в начале или в конце. Так что он получается из неправильного длины $n$ приписыванием произвольной цифры слева или справа. Но как понять, сколько раз посчитаем одно и то же?

[Math_er]

AVV
Начните с подсчета количества кортежей, у которых соседние цифры отличаются ровно на 1. Пусть длина кортежа $n,$ элементы (цифры) кортежа $a_i\in\{0,1,2\}.$
Для начала выберем $a_1=1.$ Докажите, что в этом случае искомое количество кортежей $a_1a_2...a_n$ равно $2^{\left\lfloor\frac{n}{2}\right\rfloor}.$
После этого остаётся заметить, что независимо от выбора $a_1$, Вы достаточно быстро придёте к единице (потому что $0\to 1,\; 2\to 1,\; 1\to 0 \to 1$ или $1\to 2 \to 1$.)

[popolznev]

Пусть $Q_n$ - число правильных кортежей длины $n$. Можно разбить все эти хорошие кортежи на три кучки: $Q_n = Q_n^0+Q_n^1+Q_n^2$, где $Q_n^j$ - число кортежей, в которых последний символ есть $j$. Понятно, что из каждого кортежа длины $n$ классов $Q_n^0$ и $Q_n^2$ получается по два хороших кортежа длины $n+1$, а из каждого кортежа длины $n$ класса $Q_n^1$ получается три хороших кортежа длины $n+1$. Таким образом, $Q_{n+1} = 2Q_n^0+3Q_n^1+2Q_n^2$. Не совсем рекуррентное соотношение, но хоть что-то для начала. Для $Q_n^j$ тоже можно выписать что-то вроде рекуррентных соотношений, только классы будут перепутываться.

А вообще есть ощущение, что это к чему-то известному сводится. Какие-нибудь там, не знаю, числа Стирлинга.

[Legioner93]

Правильные посчитать проще
Пусть $(0_n, 1_n, 2_n)$ -- количество правильных кортежей длины $n$ с соответствующей цифрой в начале. Попробуем построить правильные кортежи длины $(n + 1)$. Неправильные длины $n$ рассматривать нет смысла, так как им уже не помочь. Любой правильный кортеж длины $(n + 1)$ содержит одну из трёх цифр в начале + правильный кортеж длины $n$.
Исходя из этого, $(0_{n+1}, 1_{n+1}, 2_{n+1})$ легко выражаются через $(0_n, 1_n, 2_n)$. Вот вам и рекуррентная формула (точнее, вас интересует $0_n + 1_n + 2_n$). Наверняка там что-то упроститься (как минимум, $0_n = 2_n$). Попробуйте так.

[AVV]

Здорово, как просто! Спасибо!

[Legioner93]

AVV
А явную формулу вам удалось получить? Смотрите, у вас
$x_{n+1} = A x_{n}$, где $x_{n} = \begin{pmatrix} 0_n \\ 1_n \end{pmatrix}$, $A$ -- матрица $2 \times 2$ из натуральных чисел.
Ну а это на самом деле почти что линейная рекуррентная последовательность (типа чисел Фибоначчи или чисел Люка).
Почти - потому что штуки вида $y_{n+2} = a y_{n+1} + b y_{n}$ преобразуются в $x_{n+1} = B x_{n}$, где $x_{n} = \begin{pmatrix} y_{n} \\ y_{n-1} \end{pmatrix}$, $B = \begin{pmatrix} a & b \\ 1 & 0 \end{pmatrix}$.
Но я думаю, вам не надо приводить $A$ к виду $B$, лучше найдите общую теорию решения $x_{n+1} = A x_{n}$ для произвольной $A$.

[AVV]

Здесь, казалось бы, наиболее удобно через трюк с характеристическим многочленом, позволяющий выразить $x_n$ как $C_1 \lambda_1{}^n + C_2 \lambda_2{}^n$.