Let $a_n$ (for $n \geq 2$) denote the number of words of length $n$ over a 7-letter alphabet in which each letter is the same as the previous or next one. Find a compact formula for $a_n$.
The conclusion is that each letter must appear in a "group" of the same letters of size 2 or more.
My first approach was by recursion and I got:
$$a_n = 7a_{n-2} + 7a_{n-3}, a_0 = 1, a_1 = 0, a_2 = 7$$
since every string of length $n$ can be created from a string of length $n-2$ by adding two identical letters, or from a string of length $n-3$ by adding three identical letters. We can achieve a group of any length in this way. Each time, we choose the color of the added letters in 7 ways.
The second way is to use stars and bars, dividing into elements $\geq 2$. At the start, we can assign 2 elements to each of the $k$ groups, so we have the standard stars and bars but for $n-2k$ elements:
$$\binom{n-2k+k-1}{k-1} = \binom{n-k-1}{k-1}.$$
Then we sum over all possible numbers of groups and assign a color to each group in 7 ways:
$$a_n = \sum_{k=1}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n-k-1}{k-1} \cdot 7^k.$$
There are at most $\left\lfloor\frac{n}{2}\right\rfloor$ groups.
However, first of all, these two solutions give different values, and secondly, I suspect that they count some things more than once, because numbers they give are slightly larger than when manually counting the possibilities.
Is any of these formulas good? If not, what could be the way to find the number of these sequences?
Thanks.
Best Answer
starting with $a_n=a_{n-1}+6a_{n-2}$ with $a_2=a_3=7$, I get... $$a_n = C_1(3)^n+C_2(-2)^n$$ which gives rise to the system... $$ 9C_1+4C_2 = 7$$ $$ 27C_1-8C_2=7$$
The solution is $C_1 = \frac 7{15}, C_2=\frac 7{10}$
So the simplified solution works out to... $$a_n = \frac 75 \bigg [ 3^{n-1}-(-2)^{n-1} \bigg ]$$
Which agrees with the answer given by @Mike Earnest but is arguably more compact.