# N choose k formula

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:

cepheid
Staff Emeritus
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)

pbuk
Gold Member
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! ##.

Thank you both, got it.

Ray Vickson
Homework Helper
Dearly Missed
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.

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
Homework Helper
Dearly Missed
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.

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

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