• Support PF! Buy your school textbooks, materials and every day products Here!

Sum of combinations

  • Thread starter ephedyn
  • Start date
  • #1
170
1

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.
 

Answers and Replies

  • #2
tiny-tim
Science Advisor
Homework Helper
25,832
249
Hi ephedyn! :smile:

(try using the X2 tag just above the Reply box :wink:)
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 = … ? :wink:
 
  • #3
170
1
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?

Thanks in advance.
 
  • #4
Dick
Science Advisor
Homework Helper
26,258
618
There is also a symmetry in the binomial coefficients. E.g. 17C1=17C16, 17C3=17C14, etc.
 
  • #5
170
1
Yep, got it! Thanks aplenty to both of you.
 
  • #6
HallsofIvy
Science Advisor
Homework Helper
41,795
925
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?
 
  • #7
170
1
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.
 
  • #8
1,838
7
You considered (1+1)^17

but you should also look at (1-1)^17
 
  • #9
tiny-tim
Science Advisor
Homework Helper
25,832
249
You considered (1+1)^17

but you should also look at (1-1)^17
Yes! :smile:
 
  • #10
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
  • #11
HallsofIvy
Science Advisor
Homework Helper
41,795
925
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.
 
  • #12
Dick
Science Advisor
Homework Helper
26,258
618
Or if you want to do the general case, even or odd, proof by induction is pretty simple.
 
  • #13
170
1
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?)
 

Related Threads for: Sum of combinations

Replies
1
Views
1K
Replies
11
Views
5K
Replies
14
Views
896
  • Last Post
Replies
5
Views
719
  • Last Post
Replies
19
Views
1K
  • Last Post
Replies
4
Views
886
  • Last Post
Replies
20
Views
1K
  • Last Post
Replies
2
Views
1K
Top