Processing math: 100%

Tuesday, 8 October 2013

A Simple Bijection between Even and Odd Subsets


Let E(n) denote the set of even subsets (subsets of even size) and O(n) the set of odd subsets (subsets of odd size) of a set S containing n elements.  Assuming n \geq 1, we can describe a simple bijection between these two sets as follows-

Let y be any arbitrary element of the set S. Then, we simply map each A \subseteq S to the set A \triangle \{y\}, the symmetric difference of the subset A and the singleton set \{y\}. In other words, if the set A does not contain the element y, then we map it to the set A \cup \{y\}; otherwise, if A already includes the element y, then we map it to the set A \setminus \{y\}.

Under this mapping, since each subset gets mapped to a subset whose cardinality is either 1 more or 1 less than its own cardinality, its easy to see that odd subsets get mapped to even subsets while even subsets get mapped to odd subsets. Moreover, since |E(n)| = |O(n)| and the mapping is one-to-one, it has to be a bijection.  

No comments:

Post a Comment