Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 ?

share|cite|improve this question

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.

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:… –  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

1 Answer 1

up vote 6 down vote accepted

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.

share|cite|improve this answer
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

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