[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
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
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
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
participants (4)
-
Andy Latto -
Dan Asimov -
Mike Speciner -
victor miller