2
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ Have you tried writing out the first few $a_n$? $\endgroup$
    – lulu
    Apr 16 '21 at 14:38
  • $\begingroup$ I did now, but it doesn't say anything to me. Also, $a_1$ should be $7$ right? $\endgroup$
    – abc2343
    Apr 16 '21 at 14:48
  • $\begingroup$ I would say $a_0=0$, but I agree it's ambiguous. Edit your post to include the sequence you have found. $\endgroup$
    – lulu
    Apr 16 '21 at 14:51
  • $\begingroup$ 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? $\endgroup$
    – lulu
    Apr 16 '21 at 14:53
  • $\begingroup$ 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$. $\endgroup$
    – JMoravitz
    Apr 16 '21 at 14:55
1
$\begingroup$

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

}
$\endgroup$
0
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.