# Counting the number of $n$-digit quaternary sequence that have even number of $0's$ and an even number of $1's$

Show that the number of $n$-digit quaternary sequences(sequences that have $0's, 1's, 2's$ and $3's$ as the digits) that have an even number of $0's$ and an even number of $1's$ is $4^n/4+2^n/2$.

The total number of sequences which don't have any $0's$ or $1's$ is $2^n$.
So out of remaining sequences($4^n-2^n$) half will have even number of $0's$.
And out of those half will have even number of $1's$. So the answer should be $2^n + (4^n-2^n)/4$.
It is not correct but I have not been able to find my mistake.
Please point out the mistake in this approach and how to solve the problem?

-
A quick way would be to get the coefficient of $x^n$ in $e^{2x} ((e^x+e^{-x})/2)^2$. –  wj32 Oct 9 '12 at 20:56
Notes on @wj32's generating function approach: a) This has the added advantage of naturally dealing with the special case $n=0$ (which the question doesn't mention). b) The result is $n!$ times the coefficient of $x^n$. –  joriki Oct 9 '12 at 22:40

You make two unjustified assertions that half the sequences in certain sets will have an even number of certain digits. Your first assertion about half of the $4^n-2^n$ sequences happens to be true, but the second assertion is false.

I'll say "zero/one" to mean a digit that is zero or one. Half of the sequences with at least one zero/one also have an even number of zeros. Why? Because flipping the last zero/one gives a bijection from {sequences with at least one zero/one and an even number of zeros} to {sequences with at least one zero/one and an odd number of zeros}.

However, amongst sequences with at least one zero/one and an even number of zeros, it is just not true that half of these sequences half an even number of ones. In particular with $n=1$ there is a unique sequence, "1", with at least one zero/one and an even number of zeros, and so all such sequences have an odd number of ones.

Here is one way to correct the argument. If a sequence has an even number of zeros and an even number of ones, it has an even number of zero/ones. So instead of considering sequences with at least one zero/one, consider sequences with a positive even number of zero/ones.

The number of sequences with an even number of zero/ones is $4^n/2$ - this can be proved by considering the possibilities for the last digit. The number of sequences with a positive even number of zero/ones is therefore $4^n/2-2^n$. By the same "flipping" argument as above, half of these sequences, $4^n/4-2^n/2$, have an even number of zeros. Adding the sequences with no zeros or ones we get $4^n/4+2^n/2$.

-
"The number of sequence with an even number of zeros/ones is $4^n/2$" here you are not considering when both zeros and ones are even.Right??? and "half of the sequence will have even number of zeros" but we need both zeros and ones even. –  Saurabh Oct 10 '12 at 7:16
Let $n_0$ be the number of zeros and $n_1$ be the number of ones. By "sequences with an even number of zeros/ones" I am referring to sequences where $n_0+n_1$ is even. Thus either $n_0$ and $n_1$ are both even, or $n_0$ and $n_1$ are both odd. –  Colin McQuillan Oct 10 '12 at 9:16
How can I prove that the number of sequences with and even number zero/ones is $4^n/2$ because I can only think of the following recurrence $$a_n=2a_{n-1}+b_{n-1}+c_{n-1}$$ where $a_n$ is the number of sequences where zeros + ones are even, $b_n$ is the number of sequence where zeros are even and ones are odd and $c_n$ are the sequences where ones are even and zeros are odd. –  Saurabh Oct 10 '12 at 16:11
Also in the second last sentence didn't you mean " have an even number of zeros and ones ".??? –  Saurabh Oct 10 '12 at 16:12
(1) The number of sequences with an even number of zero/ones is $4^n/2=4^{n-1}\cdot 2$ because you can choose the first $n$ digits arbitrary (so $4^{n-1}$ choices), then you are constrained to either use a zero/one or a two/three for the last digit, and in either case there are two choices. (2) If $n_0+n_1$ is even and $n_0$ is even then $n_1$ is even. –  Colin McQuillan Oct 10 '12 at 16:15

Set up a system of recurrences. You have four cases, call even 0, odd 1; denote the number of sequences of length $n$ and parities $x y$ by $s_{x y}^{(n)}$. Considering how you can make up the strings (add 0, add 1, add 2 or 3) you have: \begin{align} s_{00}^{(n + 1)} &= 2 s_{00}^{(n)} + s_{01}^{(n)} + s_{10}^{(n)} \\ s_{01}^{(n + 1)} &= s_{00}^{(n)} + 2 s_{01}^{(n)} + s_{11}^{(n)}\\ s_{10}^{(n + 1)} &= s_{00}^{(n)} + 2 s_{10}^{(n)} + s_{11}^{(n)} \\ s_{11}^{(n + 1)} &= s_{01}^{(n)} + s_{10}^{(n)} + 2 s_{11}^{(n)} \end{align} You are interested only in $s_{00}^{(n)}$. You also have $s_{00}^{(0)} = 1$, and $s_{01}^{(0)} = s_{10}^{(0)} = s_{11}^{(0)} = 0$.

Define the generating functions $$S_{xy}(z) = \sum_{n \ge 0} s_{xy}^{(n)} z^n$$ Multiply the recurrences by $z^n$, add over $n \ge 0$ and recognize e.g.: $$\sum_{n \ge 0} s_{xy}^{(n + 1)} z^n = \frac{S_{xy}(z) - s_{xy}^{(0)}}{z}$$ to get a system of equations in the functions $S_{xy}(z)$. Solving this gives: $$S_{00}(z) = \frac{1}{4} + \frac{1}{2} \cdot \frac{1}{1 - 2 z} + \frac{1}{4} \cdot \frac{1}{1 - 4 z}$$ This is just geometric series, except for the constant term, which appears only when $n = 0$; use Iverson's convention to represent it: $$s_{00}^{(n)} = \frac{1}{4} \cdot [n = 0] + 2^{n - 1} + 4^{n - 1}$$ This matches hand count: \begin{align} 0 & 1 & \\ 1 & 2 & 2, 3 \\ 2 & 6 & 00, 11, 22, 23, 32, 33 \\ 3 & 20 & 002, 003, 020, 030, 112, 113, 121, 131, \\ & & 200, 211, 222, 223, 232, 233, 300, 311, 322, 323, 332, 333 \end{align}

-