12
$\begingroup$

Let $|X|=n$. How to find all number of subsets $X$ consisting of an even number of elements?

$\endgroup$
1

3 Answers 3

14
$\begingroup$

Here's a quick combinatorial method.

If $n=0$ then clearly there is $1$ such subset, namely the empty set itself.

If $n>0$, list the elements of $X$ as $$x_1, x_2, \dots, x_n$$ A subset $S \subseteq X$ with an even number of elements is determined by its intersection with $\{ x_1, \dots, x_{n-1} \}$: if the intersection has an even number of elements then $x_n \not \in S$, and if it has an odd number of elements then $x_n \in S$.

Thus the number of subsets of $X$ with an even number elements is equal to the number of subsets of $\{ x_1, \dots, x_{n-1} \}$, namely $2^{n-1}$.


Alternatively, convince yourself that the number of subsets with an even number of elements is $$\frac{1}{2} \left( \sum_{k=0}^n \binom{n}{k} + \sum_{k=0}^n (-1)^k \binom{n}{k} \right)$$ and apply the binomial theorem.

$\endgroup$
8
$\begingroup$

In total there are $2^n$ subsets of $X$.

If $n$ is odd then there is a one-to-one correspondence between sets with even cardinality and sets with odd cardinality. Subset $S$ corresponds with its complement. Consequently the number of subsets with even cardinality equals the number of subsets with odd cardinality. So this number is $\frac122^n=2^{n-1}$.

If $n$ is even then put one element $x_0\in X$ aside. With the trick described above we find that $X-\{x_0\}$ has $2^{n-2}$ subsets with even cardinality and also $2^{n-2}$ subsets with odd cardinality. The subsets of $X-\{x_0\}$ with odd cardinality become subsets $X$ with even cardinality if element $x_0$ is added to each of them. This gives us $2^{n-2}+2^{n-2}=2^{n-1}$ subsets of $X$ with even cardinality.

So in both cases the answer is $2^{n-1}$.

$\endgroup$
1
$\begingroup$

Hint

There is $\displaystyle\binom{n}{2k}$ different sets of size $2k$ for $1 \leq k \leq n/2$.

Formulate then your result as a sum and simplify it.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .