Combinatorial Bijection?

I have the following problem, which seems pretty easy, but I'm not sure as to what exactly is meant by a combinatorial bijection. I know what a 'normal' bijection is. The problem and my work follows beneath.

Let $H$ denote the number of ones in a binary string. Give a combinatorial bijection between the set of all binary strings of length $n$ and even $H$ and the set of those that have the same length $n$ and odd $H$.

As for every place in a binary string there are $2$ possibilities, the cardinality of a set of binary strings of length $n$, call this set $S$, is obviously $2^{n}$, corresponding to strings ranging from $H=0$ to $H=(n-1)$. $2^n$ is an even number, so we can partition $S$ into two sets of the same cardinality, one of strings with $H$ even and one with strings of odd $H$. Then just create an arbitrary injective matching and we've got our bijection.

• did you show why those two sets have the same cardinality? I think that is the point of the question – Evan Oct 23 '13 at 2:58

It's clear that this construction requires $n\ge1$, and there is no such bijection when $n=0$; the one and only null string has even $H$. Algebraically, the difference between the number of strings with even $H$ and the number with odd $H$ is$$\binom n0-\binom n1+\binom n2-\binom n3+\dots.$$Setting $x=1,y=-1$ in the expansion of $(x+y)^n$, we find that the displayed sum, which is equal to the number of strings with even $H$ minus the number with odd $H$, is also equal to $0^n$. Observe that $0^n$ is the correct answer in all cases, since $0^n=0$ when $n\gt0$, and $0^0=1$.