This is easiest to see by looking at bit vectors of length n instead of subsets. If x,c are two bit vectors of length n, then w(x+c) = w(x) + w(c) mod 2 where w is the Hamming weight, and the + inside the w is the mod 2 sum in each coordinate. x--> x+c is an involution (so it's certainly a bijection) Your bijection comes from the case where c is the all 1's vector, which doesn't work when n is even. Victor 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.
(If we set S = {1,...,n} and each subset X = {a,b,...,c} where a < b < ... < c, then one can certainly list the elements of E by size and, within each size, by lexicographic ordering, and likewise for O. This defines a bijection E -> O. But that's less natural than just taking each subset to its complement.)
QUESTION: Exactly how is "natural" defined so that complementation is a natural bijection E -> O for n odd, but there is no known natural bijection E -> O for the case of n even?
Dan
_____________________________________________________________________ "It don't mean a thing if it ain't got that certain je ne sais quoi." --Peter Schickele
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun