Find number of sequences of 7 letters such that every letter is equal to previous or next

Question

Let $a_n$ be such sequence of $7$ letters, such that every letter is equal to previous or next letter in that sequence. My idea is to find recursive formula for $a_n$ and then to write generating function for $a_n$. From that I can find general formula for $a_n$. I have two cases:

– If $a_{n-1}$ ends with two same letters, then I can put any letter at $n$-th position.

– If $a_{n-1}$ ends with two different letters, then at $n$-th position I can put only one letter (same as at $(n-1)$-th position).

So I have recursive formula:

$a_n = 7 \cdot (\text{number of sequences $a_{n-1}$ such that two last letters are the same}) + (\text{number of sequences $a_{n-1}$ such that two last letters are different} )$

I don't where to go from here. Thanks in advance for any clues.

Answer 1

I think there is a slight problem with the recurrence, because the last letter always has to be equal to the previous one.

So to "fix" this we count a slightly different set of sequences that can be extended more naturally. Let $f_n$ be the number of sequences such that every letter except the last one must be equal to one of its neighbours.

We wish to find a recurrence for $f_n$.

The number of sequences that end in two consecutive equal ones is $f_{n-1}$.

The number of sequences that do not end in two consecutives is $ 6 \cdot f_{n-2}$.

To see this notice that every sequence counted in $f_{n-2}$ can be extended in exactly $6$ ways to a sequence of length $n$ where the last two are not equal, this is because the term $n-1$ must be equal to the term $n-2$.

Hence we get $f_n = f_{n-1} + 6f_{n-2}$.

We have $f_1 = 7$ and $f_2 = 7$.

It follows : $f_3 = 49,f_4 = 91, f_5 = 385, f_6 = 931$

Your answer is $f_6=931$.

C++ bruteforce code to check the answer to the original problem (which should equal $f_{n-1}$ for $n\geq 2$)

#include <iostream>
using namespace std;

const int MAX = 10;
int C[MAX];

int next(int n,int m){
        for(int i=n-1;i>=0;i--){
                if( C[i]+1 < m){
                        C[i] ++;
                        for(int j=i+1;j<n;j++){
                                C[j] = 0;
                        }
                        return 1;
                }
        }
        return 0;
}

int count(int n,int m){
        for(int i=0;i<n;i++){
                C[i] = 0;
        }
        int start = 1;
        int res = 0;
        while( start || next(n,m) ){
                start = 0;
                int fail = 0;
                for(int i=0;i<n;i++){
                        if( (i-1 >= 0 && C[i-1] == C[i] ) || (i+1<n && C[i+1] == C[i] ) ) continue;
                        fail = 1;
                }
                if( fail == 0) res ++;
        }
        return res;
}

int main(){
        int m = 7;
        for(int n=2;n<MAX;n++){
                cout << count(n,m) << endl;
        }

}

Answer 2

To obtain a simple recursion:

Remark that each good word of length $n$ must begin with a string of the form $X^k$ for $1<k≤n$. If $k<n$ then it must begin with a string of the form $X^kY$ for some $Y\neq X$. Of course, the word that begins with that $Y$ must be a good string of length $n-k$ that does not start with $X$.

By symmetry, there are $\frac 67a_n$ good words of length $n$ that begin with something other than a specified character.

It follows that $$a_n=7+6\sum_{k=2}^{n-2} a_k=7+6a_{n-2}+6\sum_{k=2}^{n-3} a_k=a_{n-1}+6a_{n-2}$$

This is easily solved to yield $$\boxed{a_n=\frac 7{30}\times \left(3\times (-2)^n+2\times 3^n\right)}$$ given that $a_2=a_3=7$.