Re: [math-fun] Biijection between the sets of even and odd subsets of an even-sized set

On Sat, Apr 18, 2009 at 2:47 PM, Dan Asimov <dasimov@earthlink.net> wrote:

Given a finite set S of size n, let E denote the set of its subsets with even size and let O denote the set of its subsets of odd size. Then it's easy to see that

#(E) = #(O).

(Expanding the LHS of (1-1)^n = 0 does the trick nicely.)

When n is itself odd, there is a simple natural bijection between E and O: just map any subset of S to its complement.

But when n is even, there doesn't seem to be anything nearly so natural.

There is no "natural" bijection, that is one that is invariant under a permutation of the elemnts of S. Proof: What does the bijection map the empty set to? An arbitrary choice is required here. -- Andy.Latto@pobox.com