0
$\begingroup$

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?

2 Answers 2

3

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.

  • 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
1

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.

  • 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