# Bijective proof for equal number of odd-sized/even-sized subsets of a finite set [duplicate]

Possible Duplicate:
Number of even and odd subsets

Let $X$ be a finite set of cardinality $n$. Let ${\cal E}$ ($\cal O$ )denote the set of all subsets of $X$ with an even (odd) number of elements. It is easy to see that $\cal E$ and $\cal O$ contain the same number of subsets ; indeed, Newton’s binomial formula gives

$$0=0^n=(1-1)^n=\sum_{k=0}^n \binom{n}{k} (-1)^k= \sum_{k \ \text{even}} \binom{n}{k} -\sum_{k \ \text{odd}} \binom{n}{k}= |{\cal E}|-|{\cal O}|$$

When $n$ is odd, there is a simpler, more combinatorial proof : $Y \mapsto X \setminus Y$ defines a bijection between $\cal E$ and $\cal O$. Is there a similar, combinatorial, bijection between $\cal E$ and $\cal O$ when $n$ is even ?

## marked as duplicate by Davide Giraudo, Asaf Karagila♦, Paul, Hagen von Eitzen, Stefan HansenFeb 4 '13 at 10:32

• Fix one element $x$. Given a set $S$, either add $x$ to it or take it out, whichever you can do. Not posting as an answer because this is almost certainly a duplicate. – Carl Feb 4 '13 at 8:34
• @Carl : please tell me if you find a duplicate, it didn’t appear in the list of "similar questions" when I was writing out the question. – Ewan Delanoy Feb 4 '13 at 8:36
• Here's the first one I found: math.stackexchange.com/questions/15591/… – Carl Feb 4 '13 at 8:39
• @Carl : right, I’ll check more carefully next time. I would have deleted this question if it didn’t have an upvoted answer already. – Ewan Delanoy Feb 4 '13 at 8:47
• @Carl: I prefer the way this question is asked and Ittay's answer over the original. – robjohn Feb 4 '13 at 9:19

First note that the claim only holds if $n>0$. There is a general combinatorial proof that works for $n$ even or odd: since $n>0$ there is at least one element in $X$, call it $x_0$. Now define $f:E\to O$ by mapping $A\in E$ to $A\cup \{x_0\}$ if $x_0\notin A$ and to $A-\{x_0\}$ if $x_0\in A$. $f$ is easily seen to have an inverse (defined in a completely analogous way to $f$'s definition), and so is a bijection.
• In fact, $f$ is its own inverse. – Ewan Delanoy Feb 4 '13 at 8:35
• note quite since the domain and codomain of $f$ are different you can't even compose $f$ with itself. – Ittay Weiss Feb 4 '13 at 8:36
• I was thinking of $f$ as a map ${\cal P}(X) \to {\cal P}(X)$ – Ewan Delanoy Feb 4 '13 at 8:37
• then sure, it is its own inverse, but that is not the $f$ I used in the proof. – Ittay Weiss Feb 4 '13 at 8:38
• Yes, in your proof there would be a second map $g: O \to E$ defined by exactly the same formula as $f$. – Ewan Delanoy Feb 4 '13 at 8:40