For what it's worth, for n even, pick some element e. We then have the natural bijection of odd and even subsets not containing e, and adding back e to each those subsets gives a seminatural bijection of odd and even subsets containing e. Note that this argument doesn't work for the empty set, but there is no bijection in that case. --ms -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com]On Behalf Of Dan Asimov Sent: Saturday, April 18, 2009 13:47 To: math-fun Subject: [math-fun] Biijection between the sets of even and odd subsets of an even-sized set 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