1
$\begingroup$

Suppose a set S has 11 elements. How many subsets of S have an even number of elements? Express your answer as a summation.

I'm not really sure how to approach this. I think the general formula for this type of question is n!/k!(n-k)! where n is 11 and k is the number we're choosing. So would we just take the summation starting at 0 to 5 of 11!/2i!(n-2i)! Or what?

  • 0
    Your suggestion answers the question as stated. The answer below shows that the sum is 1024.2010-11-08

2 Answers 2

6

If you can use the identity:

$\sum_{k = 0}^{n} (-1)^{k} {n \choose k} = 0$

then you can show that the cardinality of the set of subsets with even cardinality is equal to the cardinality of the set of subsets with odd cardinality.

  • 0
    Wait so is my answer correct? I'm not understanding your answer..2010-11-08
  • 0
    @fprime: your answer is correct, but Unreasonable Sin is offering you a big shortcut: if the total number of subsets with an even number of elements is *the same* as the total number of subsets with an odd number of elements, *and* you know how many subsets there are *total*, then this gives you a much simpler formula for finding the number you want, instead of having to do a sum of five things.2010-11-08
  • 0
    How do I know that the number of even and odd subsets are equal?2010-11-08
  • 0
    Yeah your answer is correct. What I was pointing out is that, if you have a set with 11 elements then there are $2^{11}$ subsets. Half of those subsets are odd and the other half are even. So the number of even or odd subsets is $2^{10}$.2010-11-08
  • 0
    Oh ok I see, but how is that we know that half of those subsets are odd and half are even?2010-11-08
  • 0
    You might want to consult a textbook about a proof of that identity I gave, but if you have a set with $n$ elements then there are ${n \choose k}$ subsets with $k$ elements. That $(-1)^{k}$ in the identity is negative if $k$ is odd and positive if $k$ is even. The sum of odd sets adds up to a negative number and the sum of even sets adds up to a positive number. When the two sums are added together they equal $0$, so they must be equal.2010-11-08
  • 1
    @fprime: Do the binomial expansion of $(1-1)^n$ to get the identity.2010-11-08
  • 0
    @fprime: When you have a subset with an odd number of elements, the complement has an even number of elements. So there are the same number of odd element subsets and even element subsets. This is just a restatement of Unreasonable Sin's remark 4 ago.2010-11-08
4

Here is a very easy way of seeing that the number of sets of even cardinality is equal to the number of sets of odd cardinality: if the total number of elements is odd (like in your case) then the map that sends a set to its complement establishes a bijection between sets of even and of odd cardinality. If the total number of elements is even, then there is the same bijection between the sets of even cardinality not containing the element 1 and the sets of odd cardinality not containing 1. Also, there is the obvious bijection between sets of even cardinality not containing 1 and those of odd cardinality containing 1, so again you have a bijection between odd and even sets.

Now, you just have to compute the total number of subsets, which I am sure you can do.