1
$\begingroup$

I had a combinatorics problem that I was hoping someone could help with:

Find and solve a recurrence relation for the number of n-digit ternary sequences in which no 1 appears to the right of any 2

To begin, I think I figured out some initial conditions, $a_1$ = 3 and $a_2$ = 8 (I'm not sure about $a_4$, but doing it by hand gets long a tedious and I'm not entirely sure 20 is correct).

I've tried to think of it in terms of the last letter (and what was before it), but I'm not sure this is the right approach. For example, my guess was that if we look at all sequences ending with 0 (and 2), we have all possibilities (that is any digit could come before it. For example, a sequence ending in 0 has 0 0, 1 0, or 2 0 as options for the last two digits in the sequence and 2 has 0 2, 1 2 and 2 2 as options), however, we only have two possibilities (0 or 1) if the sequence ends in 1 (The sequence can end with either 1,1 or 0,1).

I'm not sure how to express this in a recurrence relation. I'm pretty sure though that it has to be non-homogenous. I would really appreciate some help! Thanks in advanced!!

P.S. Because recurrence relations are so confusing, a detailed explanation in your answer would be helpful! Let me know if you have any questions or concerns! Thanks!

$\endgroup$
2
$\begingroup$

Introduce an auxiliary variable: let $b_n$ be the number of ternary sequences of length $n$ that do not contain a $2$. If a sequence of length $n$ contains a $2$, you can append a $0$ or a $2$; if it does not contain a $2$, you can append a $0$, a $1$, or a $2$. In particular, you can always append a $0$ or a $2$, and if it does not contain a $2$, you can also append a $1$. Thus,

$$a_{n+1}=2a_n+b_n\;.$$

Clearly $b_{n+1}=2b_n$, and in fact it’s not hard to see that $b_n=2^n$: you’re just counting binary strings of length $n$. Thus, $$a_{n+1}=2a_n+2^n\;.$$

I’ll leave the solution to you for now.

$\endgroup$
6
  • $\begingroup$ Could you explain why $b_{n+1} = 2b_n$? Sorry, and thanks for your help! $\endgroup$ – Billy Thorton Nov 20 '13 at 4:16
  • $\begingroup$ @Billy: Sorry: I defined $b_n$ exactly backwards. I meant to make it the sequences that do not contain a $2$. I’ve fixed it now; does it make better sense? $\endgroup$ – Brian M. Scott Nov 20 '13 at 4:18
  • $\begingroup$ It makes better sense, but I'm still not sure why $b_{n+1} = 2b_n$ and not $b_{n+1} = 3b_n$ because as you said you can append any of three digits? $\endgroup$ – Billy Thorton Nov 20 '13 at 4:26
  • $\begingroup$ @Billy: But if you append a $2$, it’s no longer a sequence that does not contain a $2$. As I said, $b_n$ is really just counting the binary sequences of length $n$. $\endgroup$ – Brian M. Scott Nov 20 '13 at 4:32
  • $\begingroup$ Okay, that makes sense! So if I was to put it in terms of $a_{n} \text{that would be } a_{n} = 2a_{n-1} + 2^n$? $\endgroup$ – Billy Thorton Nov 20 '13 at 4:38

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.