Find Sum of Combinations of Odd Cardinalities in X

[ephedyn]

Homework Statement

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

Homework Equations

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]

Hi ephedyn!

(try using the X² 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)ⁿ = ∑ etc

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

 

[ephedyn]

Hi ;)

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

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

Or would you advise me to write the rewrite the form ∑¹⁷C_1+2k1^17-k1^k with dummy variable k from k=0 to 17 so that I immediately yield the result (1+1)¹⁶?

Thanks in advance.

 

[Dick]

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

 

[ephedyn]

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

 

[HallsofIvy]

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?

 

[ephedyn]

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.

 

[Count Iblis]

You considered (1+1)^17

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

 

[tiny-tim]

You considered (1+1)^17

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

Yes!

 

[Dick]

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]

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]

Or if you want to do the general case, even or odd, proof by induction is pretty simple.

 

[ephedyn]

Wow, thanks for the various methods offered. They're all very simple and elegant, and I really appreciate the general notions you're all teaching me as they're most useful in these types of questions.

On a last note, I can understand the bijection using nCk = nC(n-k), (1-1)^n and followed by proof by induction, but...

HallsofIvy: Hm, is it possible to proceed with this method if X has even cardinality? (For every subset A of X, complement(A) has same parity as that of A - this does not seem to demonstrate the desired equality?)