2
$\begingroup$

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?

  • 0
    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$.2012-10-09

2 Answers 2

2

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

  • 1
    (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.2012-10-10
1

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}