A question about a simple combinatorial problem I am reading "Introduction to Combinatorial Mathematics" by C. L. Liu.
And I cannot understand the meaning of "because of symmetry" in the following sentences:
p.7 Example 1-9
"A binary sequence is a sequence of $0$'s and $1$'s. What is the number of $n$-digit binary sequences that contain an even number of $0$'s(zero is considered as an even number) ? The problem is immediately solved if we observe that because of symmetry half of the $2^n$ $n$-digit binary sequences contain an even number of $0$'s, and the other half of the sequences contain an odd number of $0$'s."
Liu says that "because of symmetry".
In fact, if $n$ is an odd integer, the problem is immediately solved by symmetry as follows(but if $n$ is an even integer, the following argment doesn't work):
If a sequence contains an even number of $0$'s, then the sequence contains an odd number of $1$'s.
If a sequence contains an odd number of $0$'s, then the sequence contains an even number of $1$'s.
So, "the number of sequeces which contain an even number of $0$'s" is equal to "the number of sequeces which contain an odd number of $1$'s",
and, "the number of sequeces which contain an odd number of $0$'s" is equal to "the number of sequeces which contain an even number of $1$'s".
Obviouly, "the number of sequeces which contain an even number of $0$'s" $+$ "the number of sequeces which contain an odd number of $0$'s" is equal to $2^n$.
And, by symmetry, "the number of sequeces which contain an even number of $0$'s" is equal to "the number of sequeces which contain an even number of $1$'s".
Finally,
$2^n$
$=$
"the number of sequeces which contain an even number of $0$'s" $+$ "the number of sequeces which contain an odd number of $0$'s"
$ = $
"the number of sequeces which contain an even number of $0$'s" $+$ "the number of sequeces which contain an even number of $1$'s"
$ = $
"the number of sequeces which contain an even number of $0$'s" $\times 2$.
So, 
"the number of sequeces which contain an even number of $0$'s" is equal to $2^{n-1}$.
 A: Let the number of binary sequences of $n$ digits such that the number of $0$s is even be $E_n$, and similarly define $O_n$ for an odd number of $0$s, with $E_n + O_n = 2^n$. Looking at the sequences of length $n-1$, there are $E_{n-1}$ that have an even number of $0$s, and $O_{n-1}$ that have an odd number.
I then claim that there are four groups of sequences of length $n$:


*

*Sequences where the first digit is $0$, and the remaining sequence of length $n-1$ has an even number of $0$s, such that the whole sequence has an odd number of $0$s (there are $E_{n-1}$ of these).

*Sequences where the first digit is $1$, and the remaining sequence has an even number of $0$s, such that the whole sequence has an even number of $0$s (there are $O_{n-1}$ of these).

*Sequences where the first digit is $0$, and the remaining sequence has an odd number of $0$s, so the whole sequence has an even number (there are $E_{n-1}$).

*Sequences where the first digit is $1$, and the remaining sequence has an odd number of $0$s, so the whole sequence has an odd number (there are $O_{n-1}$).


So the sequences with an even number of $0$s come from groups 2 and 3, while the ones with an odd number come from groups 1 and 4. But the total size of groups 2 and 3 is $E_{n-1} + O_{n-1}$, as is the size of groups 1 and 4, so the two groups are of equal size, and hence $E_n = O_n$.
A: The "symmetry" alluded to here is the symmetry between the sets, 
\begin{align*}
E &\equiv \{\mathbf{x} \in \{0, 1\}^{\times n} \ | \ \mathrm{number \ of \ 0's \ in \ \mathbf{x} \ even} \} \\
O &\equiv \{\mathbf{x} \in \{0, 1\}^{\times n} \ | \ \mathrm{number \ of \ 0's \ in \ \mathbf{x} \ odd} \} \rm{,}
\end{align*}
the sets of binary sequences with even and odd numbers of $0$'s, respectively. Symmetry means that, to every member $\mathbf{x} \in E$, we can associate exactly one member $\mathbf{y} \in O$. This can be done by, say, flipping the last bit $x_n$ of $\mathbf{x}$, which either increases the number of $0$'s by one (if $x_n = 1$) or decreases the number of $0$'s by one (if $x_n = 0$). In either case, the new sequence, $\mathbf{y}$, has an odd number of $0$'s. It is clear that every such $\mathbf{y}$ can be obtained this way (for any $\mathbf{y} \in O$, we can easily give the corresponding $\mathbf{x}$ by flipping $y_n$ back to $x_n$), and no such $\mathbf{y}$ has more than one corresponding $\mathbf{x}$. Therefore, this association defines a bijection, and so $E$ and $O$ must contain the same number of elements. Since every binary sequence of length $n$ has either an even or odd number of $0$'s, $E$ and $O$ must in fact each contain exactly half of the binary sequences of length $n$.
As a simple example, consider the case for which $n = 2$, where we have
\begin{align*}
E &= \{00, 11\} \\
O &= \{01, 10 \} \rm{.}
\end{align*}
By this mapping, the first element listed in $E$ is associated to the first element listed in $O$, and similarly for the second elements. In the same way, we check that the bijection holds for $n = 3$
\begin{align*}
E &= \{001, 010, 100, 111 \} \\
O &= \{000, 011, 101, 110\} \rm{,}
\end{align*}
and so forth.
A: The claim is that one can conclude "by symmetry" that:
Half of the $2^n$ $n$-digit binary sequences contain an even number of $0\text{'s},$ and the other half of the sequences contain an odd number of $0\text{'s}.$
A key thing to notice, which motivates the eventual answer, is that actually the claim is not true for $n=0\!:$ In fact, there's exactly one $0$-digit binary sequence, namely the empty string.  Since the number of sequences of length $0$ is odd, it's obvious that exactly half of them can't have an even number of $0\text{'s},$ since half of an odd number isn't a whole number!
[The empty string (the only binary sequence of length $0)$ has an even number of $0\text{'s}$ in it, so there's $1$ sequence of length $0$ with an even number of $0\text{'s},$ and there are $0$ sequences of length $0$ with an odd number of $0\text{'s}.]$
In any case, the claim not being true for $n=0$ suggests that any symmetry argument can't really be based on the entire string, since one would expect a general string-based symmetry argument to work for $0$-length strings as well as for strings of positive length.
However, we can use a symmetry argument based on a particular bit in the sequence rather than on the entire string (and, as long as $n\gt 0,$ there will be a bit to work with).
So let $S$ be the set of finite sequences of $0\text{'s}$ and $1\text{'s}$ of length at least $1,$ and define a function $f\colon S\to S$ by letting $f(x)$ be the same sequence as $x$ except with the first bit negated (so the first bit in $f(x)$ is $1$ minus the first bit in $x,$ and all the other bits in $f(x)$ are the same as the corresponding bits in $x).$
You can see that, for each $n\ge 1,$ $f$ defines a 1-1 correspondence between the set of $n$-digit binary sequences with an even number of $0\text{'s}$ and the set of $n$-digit binary sequences with an odd number of $0\text{'s}.$
