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

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?

• Easier to go from $T_{n-2}$ to $T_n$ by inserting either two of "$0$"s or two of "$1$"s. This maintains the invariant that there are an even number of each of zeroes and ones. The question is, how many distinct places can you insert them? May 1 '14 at 3:20
• Alternatively, how many "$2$"s are there in a sequence length $n$, ($n$ even: an even number; $n$ odd: an odd number) How can they be distributed around? Of the remaining elements what choices for $k$ of these are zeroes and $\ell$ of these are ones, and how many ways can those be permuted? May 1 '14 at 3:22
• For the first comment, does that imply that $T_n = 2(T_{n-2})$? May 1 '14 at 3:45
• Absolutely not: $2 \rightarrow 002, 020, 200$. May 1 '14 at 3:47
• Sorry, of course that is wrong. What does this comment mean "n even: an even number"? May 1 '14 at 3:48

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.

• Your system of recurrences gives a system of equations for generating functions, solve for them and you get a generating function for the result. May 1 '14 at 22:24
• Yes, that is a good way to do it. However, in this case we can get a simple closed form, which is probably best. May 1 '14 at 22:59

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.

• I've added a solution which gives your formula almost instantly by setting up a bijection. May 1 '14 at 12:27

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$$