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!

N choose k formula

  1. Sep 5, 2013 #1
    I always see two formulas for n choose k

    the first one:

    ## \dfrac{n(n-1)(n-2)...(n-k+1)}{k!} ## and the second ## \dfrac{n!}{k!(n-k)!} ## just curious on how you get from one to the other

    I multipled the first one by (n-k)! and got ## \dfrac{n(n-1)(n-2)...(n-k+1)(n-k)!}{k!(n-k)!} = \dfrac{n(n-1)(n-2)...(n-k+1)!}{k!(n-k)!} ## but not sure how to proceed... thanks
     
    Last edited: Sep 5, 2013
  2. jcsd
  3. Sep 5, 2013 #2

    cepheid

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The *definition* of n! is n*(n-1)*(n-2)*...*3*2*1

    The *definition* of (n-k)! is (n-k)*(n-k-1)*(n-k-2)*...*3*2*1

    So, the *ratio* of (n!)/(n-k)! would be

    [n*(n-1)*(n-2)*...*3*2*1] / [(n-k)*(n-k-1)*(n-k-2)*...*3*2*1]


    Comparing the two things in square brackets, every factor after n-k cancels between the numerator and the denominator. So, only factors larger than n-k remain in the numerator. So, what's left in the numerator would be n*(n-1)*(n-2)*...*(n-k+1)

    EXAMPLE: n = 10, k = 3

    n! = 10*9*8*7*6*5*4*3*2*1

    (n-k)! = 7*6*5*4*3*2*1

    dividing the two, we see that all factors below (n-k)= 7 cancel between the numerator and denominator, leaving you with 10*9*8. Notice that 8 = (n-k+1)
     
  4. Sep 5, 2013 #3
    Just expand ## (n-k)! ## in the expression on the left hand side of the equals (the expression on the right hand side is a step backwards) and compare the numerator with ## n! ##.
     
  5. Sep 5, 2013 #4
    Thank you both, got it.
     
  6. Sep 5, 2013 #5

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You did not multiply by ##(n-k)!## (nor should you). You merely expanded out ##n!## to get
    [tex] \frac{n!}{k! (n-k)!} = \frac{n(n-1) \cdots (n-k+1) (n-k)!}{k! (n-k)!}.[/tex]
    Just cancel out the factors ##(n-k)!## from the numerator and denominator.
     
  7. Sep 5, 2013 #6
    I did multiply out... I'm not sure what you mean

    I don't see how to cancel out factors from this:

    ## \dfrac{n(n-1)(n-2)...(n-k+1)(n-k)(n-k-1)(n-k-2)!}{k!(n-k)(n-k-1)(n-k-2)!} ## all I see is the (n-k)! cancelling out

    I'm trying to undersand how to get from ## \frac{n!}{k! (n-k)!} = \frac{n(n-1) \cdots (n-k+1)}{k!} ##
     
  8. Sep 5, 2013 #7

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    No. If you had multiplied by (n-k)! you would have written
    [tex] \frac{n! (n-k)!}{(n-k)! k!} = \frac{n(n-1) \cdots (n-k+1) [(n-k)!]^2}{(n-k)! k!}.[/tex]
    That is not what you wrote.
     
  9. Sep 5, 2013 #8
    I done this by using cephids eample...

    ## \dfrac{n!}{k!(n-k)!} = \dfrac{n(n-1)(n-2)!}{k!(n-k)(n-k-1)(n-k-2)!} = \dfrac{n(n-1)(n-2)...(n-k+1)}{k!} ##
     
  10. Sep 5, 2013 #9
    I multiplied ## \dfrac{n(n-1)(n-2)...(n-k+1)}{k!} ## by ## (n-k)! ## obtaining ## \dfrac{n(n-1)(n-2)...(n-k+1)(n-k)!}{k!(n-k)!} ## sorry for not being more clear
     
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: N choose k formula
  1. Formula y=kx+n help (Replies: 12)

Loading...