1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sum of combinations

  1. May 26, 2009 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant equations

    None.

    3. 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.
     
  2. jcsd
  3. May 26, 2009 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi ephedyn! :smile:

    (try using the X2 tag just above the Reply box :wink:)
    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:
     
  4. May 26, 2009 #3
    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.
     
  5. May 26, 2009 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    There is also a symmetry in the binomial coefficients. E.g. 17C1=17C16, 17C3=17C14, etc.
     
  6. May 26, 2009 #5
    Yep, got it! Thanks aplenty to both of you.
     
  7. May 26, 2009 #6

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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?
     
  8. May 26, 2009 #7
    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.
     
  9. May 26, 2009 #8
    You considered (1+1)^17

    but you should also look at (1-1)^17
     
  10. May 26, 2009 #9

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Yes! :smile:
     
  11. May 26, 2009 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  12. May 26, 2009 #11

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  13. May 26, 2009 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Or if you want to do the general case, even or odd, proof by induction is pretty simple.
     
  14. May 29, 2009 #13
    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?)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Sum of combinations
  1. Combinations -. (Replies: 4)

  2. Permutation combination (Replies: 11)

Loading...