1
$\begingroup$

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.

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

You’re being asked to exhibit some specific bijection between the two sets, thereby showing that they have the same cardinality. Combinatorial here doesn’t really modify bijection: it’s just an ordinary bijection, but it serves a combinatorial purpose.

In this case you could, for example, show that the map that change one fixed bit of the string — the first, the last, whatever — is a bijection between the two sets.

$\endgroup$
  • $\begingroup$ Makes perfect sense; thanks! $\endgroup$ – Newb Oct 23 '13 at 3:12
  • $\begingroup$ @Newb: You’re welcome! $\endgroup$ – Brian M. Scott Oct 23 '13 at 3:15
1
$\begingroup$

I think they want the definition of the bijection to be more direct and natural rather than arbitrary. For example, flip the first bit in the string.

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.