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 Hansen Feb 4 '13 at 10:32

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ 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. $\endgroup$ – Carl Feb 4 '13 at 8:34
  • $\begingroup$ @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. $\endgroup$ – Ewan Delanoy Feb 4 '13 at 8:36
  • $\begingroup$ Here's the first one I found: math.stackexchange.com/questions/15591/… $\endgroup$ – Carl Feb 4 '13 at 8:39
  • $\begingroup$ @Carl : right, I’ll check more carefully next time. I would have deleted this question if it didn’t have an upvoted answer already. $\endgroup$ – Ewan Delanoy Feb 4 '13 at 8:47
  • $\begingroup$ @Carl: I prefer the way this question is asked and Ittay's answer over the original. $\endgroup$ – 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.

  • 2
    $\begingroup$ In fact, $f$ is its own inverse. $\endgroup$ – Ewan Delanoy Feb 4 '13 at 8:35
  • $\begingroup$ note quite since the domain and codomain of $f$ are different you can't even compose $f$ with itself. $\endgroup$ – Ittay Weiss Feb 4 '13 at 8:36
  • $\begingroup$ I was thinking of $f$ as a map ${\cal P}(X) \to {\cal P}(X)$ $\endgroup$ – Ewan Delanoy Feb 4 '13 at 8:37
  • $\begingroup$ then sure, it is its own inverse, but that is not the $f$ I used in the proof. $\endgroup$ – Ittay Weiss Feb 4 '13 at 8:38
  • $\begingroup$ Yes, in your proof there would be a second map $g: O \to E$ defined by exactly the same formula as $f$. $\endgroup$ – Ewan Delanoy Feb 4 '13 at 8:40

Not the answer you're looking for? Browse other questions tagged or ask your own question.