How can we find a recurrence relation for the number of strings of length $n$ in base $3$ such that the number of $1$'s and $2$'s are odd?
Recurrence relation for the number of strings of length $n$ in base $3$
2 Answers
Let $a_n$ be the number of ternary strings of length $n$ having an odd number of $1$’s and an odd number of $2$’s. (Call such strings good strings.) Let $b_n$ be the number of ternary strings of length $n$ having an odd number of $1$’s and an even number of $2$’s, let $c_n$ be the number of ternary strings of length $n$ having an even number of $1$’s and an odd number of $2$’s, and let $d_n$ be the number of ternary strings of length $n$ having an even number of $1$’s and an even number of $2$’s.
Suppose that $\sigma$ is a good string of length $n\ge 2$, and $\tau$ is the substring consisting of the first $n-2$ digits of $\sigma$. If the last two digits of $\sigma$ are $00,11$, or $22$, then $\tau$ is counted in $a_{n-2}$. If the last two digits of $\sigma$ are $02$ or $20$, then $\tau$ is counted in $b_{n-2}$. Continuing this analysis leads to the conclusion that
$$\begin{align*} a_n&=3a_{n-2}+2b_{n-2}+2c_{n-2}+2d_{n-2}\\ &=a_{n-2}+2(a_{n-2}+b_{n-2}+c_{n-2}+d_{n-2})\;, \end{align*}$$
where the quantity in parentheses is easily evaluated explicitly to give the desired recurrence.
-
0Thanks.Can i write $a_{n-2}=b_{n-2}=c_{n-2}=d_{n-2}$? and , if no, How does it work for get $a_{n}$? – 2012-12-28
-
1@SaliMe: You most certainly cannot write $a_n=b_n=c_n=d_n$, because then the _total_ number of strings (of _any_ kind) would be a multiple of four, which it isn't (no power of $3$ is ever a multiple of $4$). – 2012-12-28
-
1@SaliMe: No, for the reason that Henning gave. In fact it turns out that $a_n=b_n=c_n=d_n-1$ when $n$ is even, and $a_n+1=b_n=c_n=d_n$ when $n$ is odd. What you *can* say is that $a_n+b_n+c_n+d_n=3^n$: there are $3^n$ ternary strings of length $n$, and each one of them is counted in exactly one of the numbers $a_n,b_n,c_n$, and $d_n$. – 2012-12-29
Suppose you select the first $n-2$ symbols arbitrarily. If those $n-2$ symbols have an odd number of 1s and an odd number of 2s, then there is exactly three ways to extend to a string of length $n$ that satisfies the condition. Otherwise there is exactly two ways to extend to a length-$n$ string.
-
0Can you explain more this statement"Otherwise there is exactly two ways to extend to a length-n string."? I think we have more cases for invalid $a_{n-2}$ --> 1)$a_{n-2}$10 and 01 2)$a_{n-2}$ 20 and 02 3)$a_{n-2}$12 and 21 – 2012-12-28
-
0@SaliMe: And in each of those three cases (of which exactly one will be true) that's exactly two ways, right? – 2012-12-28
-
0I don't understand.can you explain with example? – 2012-12-28
-
0@SaliMe: The example is in your own comment! Depending on what invalid string $a_{n-2}$ is, there are either exactly two possible ways to complete it (namely 10 and 01), or exactly two possible ways to complete it (namely 20 and 02), or exactly two possible ways to complete it (namely 12 and 21). Therefore, for _any_ invalid $a_{n-1}$, there are exactly two possible ways to complete it. – 2012-12-28
-
0$a_n = 2 a_{n-1}+3 a_{n-2} $ is it correct? – 2012-12-28
-
0@SaliMe: Um, what? I thought $a_{n-2}$ was your notation for the arbitrarily chosen (non-valid) _string_ of length $n-2$ we're trying to extend to a valid string of length $n$. What does it mean for you to multiply such things with numbers? – 2012-12-28
-
0Can you write out to get recurrence relation? I really can not get the relation. – 2012-12-28
-
0@SaliMe: Come on. How many strings of length $n-2$ are there? How many of these are valid (and therefore can be extended in 3 ways each)? How many of them are invalid (and therefore can be extended in 2 ways each)? – 2012-12-28
-
0we have $3^{n-2}$ strings of length $n-2$ and $3(3^{n-2}-a_{n-2})$ that can be extended. I don't understand how to get 2 ways? – 2012-12-28
-
0@SaliMe: Look at **your own very first comment in this thread**. You're enumerating **yourself** what the 2 ways are in different cases. – 2012-12-28