1. Not finding help here? Sign up for a free 30min 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!

Permutation Proof

  1. Jun 27, 2013 #1
    1. Prove the following identity:
    Ʃ(n choose k)(m-n choose n-k) = (m choose n)
    from k = 0 to k = n


    I've tried induction, and just played around with a few properties of permutations, but nothing seems to satisfy the proof, any ideas?
     
  2. jcsd
  3. Jun 27, 2013 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Brandon1994! :smile:

    If you choose n things from m,

    how many of those n will be in the first n, and how many will be in the last n-m ? :wink:
     
  4. Jun 27, 2013 #3

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I would use a direct approach: Show that the left side is the number of ways to choose n elements out of a set of m elements. The sum is very intuitive if you see what it does.

    Edit: tiny-tim, don't make it too easy ;).
     
  5. Jun 27, 2013 #4

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hi mfb! :smile:

    i assumed he'd already tried to split the sum, and needed an extra hint :wink:
     
  6. Jun 27, 2013 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper



    Hint: (n choose k) is called the binomial coefficient for a good reason: it appears in the binomial expansion! Exploit that fact.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Permutation Proof
Loading...