How do you derive the two n choose k formulas?

[zoxee]

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

 

[cepheid]

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)

 

[pbuk]

not sure how to proceed

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!$.

 

[zoxee]

Thank you both, got it.

 

[Ray Vickson]

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

You did not multiply by $(n-k)!$ (nor should you). You merely expanded out $n!$ to get
$$\frac{n!}{k! (n-k)!} = \frac{n(n-1) \cdots (n-k+1) (n-k)!}{k! (n-k)!}.$$
Just cancel out the factors $(n-k)!$ from the numerator and denominator.

 

[zoxee]

You did not multiply by $(n-k)!$ (nor should you). You merely expanded out $n!$ to get
$$\frac{n!}{k! (n-k)!} = \frac{n(n-1) \cdots (n-k+1) (n-k)!}{k! (n-k)!}.$$
Just cancel out the factors $(n-k)!$ from the numerator and denominator.

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!}$

 

[Ray Vickson]

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

No. If you had multiplied by (n-k)! you would have written
$$\frac{n! (n-k)!}{(n-k)! k!} = \frac{n(n-1) \cdots (n-k+1) [(n-k)!]^2}{(n-k)! k!}.$$
That is not what you wrote.

 

[zoxee]

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!}$

 

[zoxee]

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