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