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

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.

• Have you tried writing out the first few $a_n$?
– lulu
Apr 16 '21 at 14:38
• I did now, but it doesn't say anything to me. Also, $a_1$ should be $7$ right? Apr 16 '21 at 14:48
• I would say $a_0=0$, but I agree it's ambiguous. Edit your post to include the sequence you have found.
– lulu
Apr 16 '21 at 14:51
• As a hint: you know that each good word begins with $X^k$ for some character $X$ and some $k>1$. If $k<n$, what can you say about what must follow?
– lulu
Apr 16 '21 at 14:53
• I would expect $a_1=0$ but $a_0=1$ personally, @lulu. I agree though that it will be easier to use $a_2$ and $a_3$ as the initial conditions as they are unambiguously equal to $7$. Apr 16 '21 at 14:55

## 2 Answers

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;
}

}


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. If $$k 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$$.