Counting problem about Palindromes 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.

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:

*

*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").


*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$.
