# Sum of combinations

## Homework Statement

Let X = {1,2,3, ... ,17}. Find the number of subsets Y of X with odd cardinalities.

None.

## The Attempt at a Solution

Well, I think I'm correct: 17C1 + 17C3 + 17C5 + ... + 17C17 = 65536

The problem is, I'm not supposed to use a calculator and I supposed to take less than 6min to get this done (maybe I'm just slow...).

So, I have 2 questions:

- I noted that 65536 = 2^16, so I guessed there should be some useful theorems to help me out with this - I did a quick search on 'combinatorial sums', but it seems like I didn't get the right description for this kind of problem. Are there some other equations that I'm supposed to be familiar with for this?

- Are there any heuristics to speed up the evaluation of combinations/permutations? The solutions to some problems that I had came across reduced to numbers like 48C12, which I could manage with prime factorization, but I felt it could have been faster.

tiny-tim
Homework Helper
Hi ephedyn!

(try using the X2 tag just above the Reply box )
17C1 + 17C3 + 17C5 + ... + 17C17 = 65536

I noted that 65536 = 2^16

General tip: when you have to add C's, try to make it something that uses the binomial theorem, (a ± b)n = ∑ etc

Specific hint: 17C1 + 17C2 + 17C3 + ... + 17C17 = … ?

Hi ;)

Oh, thanks for both tips! To follow up on your hint, I have
17C1 + 17C2 + 17C3 + ... + 17C17
= (1+1)17 - 17C0
= 217 - 1

Could I ask you for a suggestion for subtracting the series 17C2 + 17C4 + 17C6 + ... + 17C16 from 217 - 1, probably to yield 217 - 216 = 216?

Or would you advise me to write the rewrite the form ∑17C1+2k117-k1k with dummy variable k from k=0 to 17 so that I immediately yield the result (1+1)16?

Dick
Homework Helper
There is also a symmetry in the binomial coefficients. E.g. 17C1=17C16, 17C3=17C14, etc.

Yep, got it! Thanks aplenty to both of you.

HallsofIvy
Homework Helper
But the basic problem is not to sum those binomial coefficients but to determine the number of subsets of odd cardinality. Is there any reason to believe that there are more subsets of even cardinality than odd, or vice-versa?

But the basic problem is not to sum those binomial coefficients but to determine the number of subsets of odd cardinality. Is there any reason to believe that there are more subsets of even cardinality than odd, or vice-versa?

Hm, I'll be led to believe that there is reason to believe that there are not more subsets of even cardinality than odd. I can't produce a proof, but I vaguely recall something like this in the preliminary chapters of one of my calculus textbooks.

But it does sound like you're leading to a very interesting topic here since the solution here would suggest that there are equal numbers of both. I'll be happy to hear your view.

You considered (1+1)^17

but you should also look at (1-1)^17

tiny-tim
Homework Helper
You considered (1+1)^17

but you should also look at (1-1)^17

Yes!

Dick
Homework Helper
Hm, I'll be led to believe that there is reason to believe that there are not more subsets of even cardinality than odd. I can't produce a proof, but I vaguely recall something like this in the preliminary chapters of one of my calculus textbooks.

But it does sound like you're leading to a very interesting topic here since the solution here would suggest that there are equal numbers of both. I'll be happy to hear your view.

You could also think about why nCk is equal to nC(n-k). Set up a 1-1 correspondence between even and odd cardinality subsets using the complement.

HallsofIvy
Homework Helper
Perhaps simpler: since 17 is odd itself, for every subset A of X, complement(A) has opposite parity to that of A: if one is even, the other is odd.

Dick