4
$\begingroup$

Find a recurrence relation for the number of strings of length $n$ over the alphabet $\{1, 2,3,4,5,6,7\}$ such that there are no consecutive $1$'s or $2$'s.

I have no idea where to start. I've been stuck for some time. Any help is appreciated, Thanks.

$\endgroup$
2
  • $\begingroup$ How can there be consecutive $0$s if there are no $0$s. $\endgroup$ – fleablood Mar 13 '19 at 23:21
  • $\begingroup$ oops, changed $0$'s to $2$'s $\endgroup$ – Adi Mar 13 '19 at 23:23
5
$\begingroup$

Make coupled recurrences, one for the number of good strings of length $n$ that do not end in $1$ or $2$ and one for the number of good strings that do end in $1$ or $2$. Given the number of each, how many strings of length $n+1$ of each type are there?

$\endgroup$
2
$\begingroup$

Building on Ross's hint.

Let $a_n$ be the number of good strings of length $n$

Let $b_n$ be the number of good strings of length $n$ which do not end in a $1$ or $2$

Let $c_n$ be the number of good strings of length $n$ which end in $1$

Let $d_n$ be the number of good strings of length $n$ which end in $2$

This gives the recurrence $a_n=b_n+c_n+d_n$

Obviously, $b_n = 5a_{n-1}$

Also we have $c_n=b_{n-1}+d_{n-1}$ because the right hand side of the equation is the number of good strings of length $n-1$ which do not end in a $1$.

Finally, $d_n=b_{n-1}+c_{n-1}$ because the right hand side of the equation is the number of good strings of length $n-1$ which do not end in a $2$

Substituting for $b_n$, $c_n$, $d_n$ in the first equation the equations we get, $a_n = 5a_{n-1}+b_{n-1}+d_{n-1}+b_{n-1}+c_{n-1}$ = $5a_{n-1}+b_{n-1}+a_{n-1}$ = $6a_{n-1}+5a_{n-2}$

Therefore, $a_n=6a_{n-1}+5a_{n-2}$

$\endgroup$
1
$\begingroup$

Strings of length $n\ge 2$ fall in two classes; those that end with a double letter, and those that do not. There are $6a_{n-1}$ strings which do not end with a double letter (six choices for the end letter, anything but the previous), and $5a_{n-2}$ which do (five choices for the double, anything but $11$ or $22$), so $$ a_{n}=6a_{n-1}+5a_{n-2},\qquad n\ge2. $$

$\endgroup$
5
  • 1
    $\begingroup$ Very neat but I think... while deleting $22$ does leave a legal string of length $n-1$, it doesn't leave all possible legal strings of length $n-1$, namely, it doesn't leave legal strings of length $n-1$ which end in $2$. A pity if I'm right though, as this is much neater than Ross's standard solution. $\endgroup$ – antkam Mar 14 '19 at 5:01
  • $\begingroup$ antkam, while Ross's solution is very neat, i think you're right. $\endgroup$ – Adi Mar 14 '19 at 11:00
  • 1
    $\begingroup$ @antkam Yep, I was way off! Oh well, with the hind sight of Adi's answer, I can now give a nice combinatorial proof of the recursion. $\endgroup$ – Mike Earnest Mar 14 '19 at 15:06
  • $\begingroup$ Great! It often (always?) happens that a set of coupled recurrences can be reduced to only 1 recurrence of the main series. I've often wondered if the single recurrence can then be "retroactively" explained -- it's lovely that you found the way in this case. If you have "general techniques" to share, I'd love to hear them. :) $\endgroup$ – antkam Mar 14 '19 at 19:07
  • 1
    $\begingroup$ @antkam No general techniques yet, though I certainly want to know them and thing they must exist. BTW, the answer to your "always?" question is yes. Any system of recurrences can be described by a vector-matrix recurrence ${\bf v}_{n+1}=A{\bf v}_n$. The characteristic polynomial of $A$ gives a univariate recurrence solved by each coordinate of ${\bf v}_n$, allowing you to decouple. $\endgroup$ – Mike Earnest Mar 14 '19 at 19:23

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.