Counting problem about Palindromes

Question

Consider the set of four digit sequences $d_1d_2d_3d_4$, where $d_i\in\{0,1,\ldots,9\}$.

(a) What is the number of all four digit sequences, which contain no palindromic subsequence. For example, the sequence $1231$ is legal but $1213$ is not. We note that a subsequence such as $22$ is considered palindromic.

(b) Can the solution of this problem can be generalized easily for $n$-digits sequences?

My attempt: First we solve the problem for $3$-digits and then use the complement principle.

Answer 1

Let's say $S$ is a string of length $n$ which satisfies the "no palindromic subsequence" rule. If we want to extend this to length $n+1$ by adding one character to the end, what all can we do:

1. The only way of violating this rule by adding a character to the end is if the last two letters become a palindrome (XX), or the last 3 letters (XYX) become one. (Note that the last 4 "XYYX" can't become a palindrome by this addition because $S$ had no palindromic subsequence, so it can't have a "YY").

2. So the new letter has basically exactly $8$ options.

The same thing is true for every such string S of length $n$.

Also, any string of length $n+1$ has to be able to be constructed this way.

So you should be able to construct a recursion $ans_n = ans_{n-1}*8$.

Answer 2

Let $F(n)$ be the number of $n$-digit sequences with this property.

For an $n+1$-digit sequence, $xabc...$, to have this property, we require $abc...$ to have the property (in which case $a\ne b$) and we then require $x\ne a$ and $x\ne b$.

Therefore, for $n\ge 2$, $F(n+1)=8F(n)$.

$F(2)=90$ and, for $n\ge 3$, $F(n)=90 \times8^{n-2}$.