Problem : There are $3^n$ n-digit sequences in which each digit is $0$, $1$ or $2$. How many of these sequences have an odd number of $0$'s ?
Let $o(n)$ = the number of n-digit sequences which have an odd number of $0$'s and
$e(n)$ = the number of n-digit sequences which have an even number of $0$'s.
Obviously $o(n) + e(n) = 3^n$ and by examples I can see that $o(n)=e(n)-1$ but I don't know how to show this.
Moreover if we have $x$ digits to choose from then by examples I see that $o(n) = e(n) – {n}^{x-2}$. And if we consider the number of sequences which have a number congruent to $0$, $1$ respectively $2$ (modulo $3$) of $0$s we see that these numbers are in arithmetic progression.
Can someone prove these assumptions to me or disprove them if they are not right?
Best Answer
One way of seeing $o(n)=e(n)-1$ (which as you noted is enough to finish): Consider the following operation, which is defined on all sequences except the all $2$ sequence:
Take the first digit which is $0/1$, and switch it between $0$ and $1$.
For example, $2101$ is mapped to $2001$. Two things which you can quickly check about this map are
Applying the map twice returns you to your original sequence. So the map effectively pairs off the $3^n-1$ sequences that aren't all $2$.
In each pair, one sequence has an even number of zeroes, the other has an odd number.
So those $3^n-1$ sequences are split evenly between even and odd. The one left over sequence has no zeroes, so is even.
The same argument works if you have $x$ digits to choose from, the only difference being that there are now $(x-2)^n$ sequences containing neither $0$ nor $1$ that aren't paired off.
In combinatorics, this sort of argument is referred to as a sign-reversing involution.