Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Question was the following:

$a_n$ is the number of ternary strings (strings of 0,1,2) which contain no consecutive zeros and no consecutive ones. Find a formula for $a_n$?

By brute force, I found a recurrence relation for $a_n$ as the following:

$a_n = 2 a_{n-1} + a_{n-2}$

Now I am wondering if there is a good combinatorial explanation/proof to my recurrence relation. Can you see something?

Best Regards

share|improve this question
2  
Terminological note: those are ternary strings, not turning strings. –  Brian M. Scott Apr 8 '13 at 20:00
    
@BrianM.Scott thank you for correction –  Xentius Apr 8 '13 at 20:02
add comment

2 Answers

up vote 7 down vote accepted

Let $b_{i,n}$ be the number of strings of length $n$ starting with $i\in\{0,1,2\}$. Then by your rules $$a_n = b_{0,n} + b_{1,n} + b_{2,n} = (b_{1,n-1} + b_{2,n-1}) + (b_{0,n-1} + b_{2,n-1}) + a_{n-1} = 2a_{n-1} + a_{n-2}.$$

ADDITION: This transformation can be translated into a proof by bijection. Let $X_n$ be the set of all sequences of length $n$. We define a map $$(X_{n-1} \times \{A,B\}) \cup X_{n-2} \quad\to\quad X_{n}$$ by ("$\cdot$" denotes concatenation; $\mu$ a sequence in $X_{n-2}$ and $\lambda$ a sequence in $X_{n-1}$):

$(\lambda,A) \mapsto 2\cdot\lambda$

$(\lambda,B)\mapsto\begin{cases} 1\cdot \lambda & \text{if }\lambda\text{ starts with }0\text{ or }2\\ 0\cdot \lambda & \text{if }\lambda\text{ starts with }1 \end{cases}$

$\mu \mapsto 0\cdot 2\cdot \mu$

This is a bijection, essentially because $(\lambda,A)$ gives all strings in $X_n$ starting with $2$, $(\lambda,B)$ gives all strings in $X_n$ starting with $10$, $01$ or $12$, and $\mu$ gives all strings starting with $02$. So $$\left|(X_{n-1} \times \{A,B\}) \cup X_{n-2}\right| = \left|X_n\right|,$$ which is $$2a_{n-1} + a_{n-2} = a_n.$$

share|improve this answer
1  
I guess what @Xentius meant by a combinatorial proof is not this. He seems to be looking for an answer like in this question he asked: math.stackexchange.com/questions/340905/… –  Amadeus Bachmann Apr 8 '13 at 19:42
    
@AmadeusBachmann exactly! –  Xentius Apr 8 '13 at 19:45
1  
@AmadeusBachmann: I think that azimut's equality has pure (and nice!) combinatorial sense. –  xen Apr 8 '13 at 19:55
    
I'm a bit baffled why my argumentation shouldn't be combinatorial. @Xentius could you please specify what kind of proof you are looking for? –  azimut Apr 8 '13 at 20:02
    
@xen I did not say azimut's proof is not combinatorial. I just wanted to say it may not be what Xentius looking for according to his previous questions. But of course only one to confirm this is Xentius. –  Amadeus Bachmann Apr 8 '13 at 20:06
show 4 more comments

Call a ternary string with no consecutive zeroes and no consecutive ones a good string. For $k=0,1,2$ let $a_n^k$ be the number of good strings of length $n$ ending in $k$. Then it’s clear that

$$\begin{align*} &a_n^0=a_{n-1}^1+a_{n-1}^2\\ &a_n^1=a_{n-1}^0+a_{n-1}^2\\ &a_n^2=a_{n-1}^0+a_{n-1}^1+a_{n-1}^2=a_{n-1}\;. \end{align*}\tag{1}$$

And now we can make the following computation:

$$\begin{align*} a_n&=a_n^0+a_n^1+a_n^2\\ &=a_n^0+a_n^1+a_{n-1}\\ &=a_{n-1}^1+a_{n-1}^0+2a_{n-1}^2+a_{n-1}\\ &=(a_{n-1}^0+a_{n-1}^1+a_{n-1}^2)+a_{n-1}^2+a_{n-1}\\ &=a_{n-1}+a_{n-1}^2+a_{n-1}\\ &=2a_{n-1}+a_{n-1}^2\\ &=2a_{n-1}+a_{n-2} \end{align*}$$

by the third line of $(1)$.

In more purely combinatorial terms the term $a_{n-1}$ in $a_n=a_n^0+a_n^1+a_{n-1}$ comes from the fact that each good string of length $n$ ending in $2$ is obtained by appending a $2$ to one of the $a_{n-1}$ good strings of length $n-1$. The rest is a little more complicated. If a good string of length $n-1$ ends in $0$ or $2$, I can append a $1$ to it to get a good string of length $n$ ending in $1$; that covers all good strings of length $n$ ending in $01$ or $21$, which is all good strings of length $n$ ending in $1$. Similarly, if a good string of length $n-1$ ends in $1$ or $2$, I can append a $0$ to get a good string of length $n$ ending in $0$, and that accounts for all good strings of length $n$ ending in $0$. Thus, to get the good strings of length $n$ ending in $0$ or $1$ I’ve used each good string of length $n-1$ ending in $0$ once, each good string of length $n-1$ ending in $1$ once, and each good string of length $n-1$ ending in $2$ twice. In other words, I’ve used each good string of length $n-1$ at least once, and I’ve used those ending in $2$ twice. Ignoring for a moment the double use of those ending in $2$, that accounts for another $a_{n-1}$ strings of length $n$. Finally, we already know that each good string of length $n-1$ ending in $2$ is just the extension by a $2$ of a good string of length $n-2$, so the double use of good strings of length $n-1$ ending in $2$ gives us another $a_{n-2}$ good strings of length $n$. Put the pieces together, and we see that $a_n=2a_{n-1}+a_{n-2}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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