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?
Best Answer
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$.