The number of length-n ternary sequences with even ones and even zeroes

Question

Just starting to appreciate recurrence relations

Let $T_n = $ number of length-n ternary sequences with an even number of ones and an even number of zeroes.

$T_0 = 1$, because $0$ is an even number, and there are zero $1$s and zero $0$s.

$T_1 = 1$, because the sequence $\{2\}$ has zero $1$s and zero $0$s

How to find $T_n$?

Possibility: split into cases.

Case 1: We have an $n$ digit sequence with an even number of $0$s and an even number of $1$s.

To get to length $n$, we have all of the length $n-1$ sequences with an even number of $0$s and $1$s, which is $T_{n-1}$

Case 2: We have an $n$ digit sequence with an odd number of $0$s and an odd number of $1$s.

Here, we basically need the total amount of length-$n$ sequences with an odd number of $0$s and an odd number of $1$. This should be $3^n - T_{n-1}$.

Case 3: We have an even number of 0s, but an odd number of 1s.

Case 4: We have an odd number of 0s, but an even number of 1s.

How to account for cases 3 and 4?

Answer 1

Consider all the strings with an even number of total ones and zeros. Let there be $k$ total one's and zeros. Then $k$ is even. Fix $k$, let’s count the number of trenary strings. First, there are ${ n \choose k}$ positions for the 1’s and 0’s, and then there are 2 choices for the value in each of these positions. The rest of the positions must be 2. Hence, there are $\sum_{ k \text{ even } } {n \choose k} 2^k $ of them.

Of these, pair them up according to those that differ only in the first non 2 digit. In this pair, clearly one of them has an even number of ones and an even number of 2's. Note that the only string not paired is the string of all 2's.

Hence, the total number of strings with an even number of 1 and even number of 0 is

$$.5 \times (-1+\sum_{ k even } {n \choose k} 2^k) +1 $$

This matches Pedro's answer.

Answer 2

Let $T_n$ be as in the post. Let $U_n$ be the number of $n$-sequences with an odd number of $0$ and an even number of $1$. Let $V_n$ be the number with an even number of $0$ and an odd number of $1$. (Note that by symmetry $U_n=V_n$.) Let $W_n$ be the number of $n$-sequences with an odd number of $0$ and an odd number of $1$. We have $$T_{n+1}=T_n +U_n+V_n.$$ This is because we can get a sequence of length $n+1$ with an even number of $0$ and of $1$ by appending a $2$ to such a sequence of length $n$, or by appending a $0$ to a sequence of length $n$ with an odd number of $0$ and an even number of $1$, or doing something similar to an $n$-sequence with an even number of $0$ and an odd number of $1$. Similarly, $$U_{n+1}=T_{n}+U_n+W_n,$$ $$V_{n+1}=T_n+V_n+W_n,$$ $$W_{n+1}=U_n+V_n+W_n.$$ A general way to attack the problem is then to express the above $4$ relationships in matrix terms, and using some linear algebra. That is, I believe, the best approach.

But we can bypass that by some manipulation. Use the fact that $V_n=U_n$ and $T_n+2u_n+W_n=3^n$. Then the first two recurrences can be rewritten as $$T_{n+1}=T_n+2U_n,$$ $$U_{n+1}=3^n-U_n.$$ Multiply each side of the first recurrence by $2$, and add. We get $$T_{n+1}+2U_{n+1}=T_n+2\cdot 3^n.\tag{1}$$ By bumping up the indices of the first recurrence by $1$, we get $$T_{n+2}=T_{n+1}+2U_{n+1}=T_{n+1}+ T_n +2\cdot 3^n-T_{n+1}=T_n+2\cdot 3^n.$$ We have reached the recurrence $$T_{n+2}=T_n+ 2\cdot 3^n.$$ This can be solved by standard methods.

Answer 3

Consider the string $\underbrace{0\cdots0}_{2i}\underbrace{1\cdots 1}_{2j}\underbrace{2\cdots 2}_{k}$, and $2i+2j+k=n$, $i,j,k\in\Bbb N_0$. Then you're looking for $$v_n=\sum_{2i+2j+k=n}\binom{n}{2i,2j,k}$$

Note $v_0=1,v_1=1,v_2=3,v_3=7,v_4=21,v_5=81,\ldots$. This can be tackled as follows.

We have $$w_n=\frac{v_n}{n!}=\sum_{2i+2j+k=n}\frac 1{(2i)!}\frac 1{(2j)!}\frac 1{k!}$$

Now we may write $$w_n=\sum_{k=0}^n\frac{1}{k!}\sum_{2i+2j=n-k}\frac{1}{(2i)!}\frac{1}{(2j)!}$$

that is $$w_n=\sum_{k=0}^n \frac{1}{k!}u_{n-k}$$ with $$u_n=\sum_{2i+2j=n}\frac{1}{(2i)!}\frac{1}{(2j)!}$$

It is evident that $u_{2n+1}=0$, $u_0=1$ and $(2n)!{u_{2n}}=\displaystyle\sum_{i=0}^n\binom{2n}{2i}=2^{2n-1},n\geqslant 1$ (this can be seen by expanding $2^{2n}$ as $(1+1)^{2n}$ and $0$ as $(1-1)^{2n}$ and killiog odd numbers by adding), so that for $n\geqslant 1$ $${v_n} = 1+\frac{1}{2}\sum\limits_{k\;\rm even>0}^n\binom nk2^{k} $$

This matches Andre's recurrence.