Количество отображений

[daogiauvang]

Найти число отображений $f: \left \{ 1, 2, 3, \cdots n \right \} \rightarrow \left \{ 1, 2, 3, 4 \right \}$, чтобы $\left | f(k+1)-f(k) \right |>1 \forall k=1 \to (n-1)$

[zhekas]

$N_1 = 4; N_2 = 6; N_{i}=N_{i-1 }+ N_{i-2}$

Получается последовательность из удвоенных чисел фибоначи $N_i = 2\cdot F_{i+2}$

[daogiauvang]

Подробнее формула $N_i$.

[zhekas]

$N14_i$ - это количество отображений, если первый его член отображается в единицу или четверку.
$N23_i$ - это количество отображений, если первый его член отображается в двойку или тройку.

Если первый член отображается в единицу или четверку. Рассмотрим для примера отображение в единицу. Тогда второй член отображается в тройку или четверку. Тогда получим
$N14_i = N23_{i-1} + N14_{i-1}$

Если первый член отображается в двойку или тройку. Рассмотрим для примера отображение в двойку. Тогда второй член отображается в четверку. Тогда получим
$N23_i = N14_{i-1}$

Тоесть получаем:
$N14_i = N14_{i-1} + N23_{i-1}$
$N23_i = N14_{i-1}$

Откуда
$N14_i = N14_{i-1} + N14_{i-2}$
$N23_i = N14_{i-1}$

$N_i = N14_i + N23_i = (N14_{i-1} + N14_{i-2}) + (N14_{i-1}) = (N14_{i-1} + N23_{i-1}) + (N14_{i-2} + N14_{i-3}) =(N14_{i-1} + N23_{i-1}) + (N14_{i-2} + N23_{i-2}) = N_{i-1} + N_{i-2}$