Ternary Strings and the Pell Numbers

Abstract

For $n\ge 1$, let $a_n$ count the number of strings $s_1{s}_2{s}_3\dots s_n$, where
(i) $s_1=0$;
(ii) $s_i\in \{0,1,2\}$ for $2\le i\le n$;
(iii) $|s_i–s_{i-1}|\le 1$ for $2\le i\le n$.

Then $a_1=1$, $a_2=2$, $a_3=5$, $a_4=12$, and $a_5=29$.

In general, for $n\ge 3$, $a_n=2a_{n-1}+a_{n-2}$, and $a_n$ equals $P_n$, the $n$th \emph{Pell} number.

For these $P_n$ strings of length $n$, we count
(i) The number of occurrences of each symbol $0,1,2$;
(ii) The number of times each symbol $0,1,2$ occurs in an even or odd position;
(iii) The number of levels, rises, and descents within the strings;
(iv) The number of runs that occur within the strings;
(v) The sum of all strings considered as base $3$ integers;
(vi) The number of inversions and coinversions within the strings; and
(vii) The sum of the major indices for the strings.