• Support PF! Buy your school textbooks, materials and every day products Here!

N choose k formula

  • Thread starter zoxee
  • Start date
  • #1
37
0
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:

Answers and Replies

  • #2
cepheid
Staff Emeritus
Science Advisor
Gold Member
5,192
36
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)
 
  • #3
pbuk
Science Advisor
Gold Member
1,378
372
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! ##.
 
  • #4
37
0
Thank you both, got it.
 
  • #5
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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
[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.
 
  • #6
37
0
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.
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!} ##
 
  • #7
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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
[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.
 
  • #8
37
0
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!} ##
 
  • #9
37
0
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
 

Related Threads on N choose k formula

  • Last Post
Replies
4
Views
1K
Replies
1
Views
999
Replies
1
Views
4K
Replies
5
Views
1K
  • Last Post
Replies
6
Views
661
  • Last Post
Replies
1
Views
2K
Replies
7
Views
2K
Replies
1
Views
4K
  • Last Post
Replies
7
Views
3K
Replies
8
Views
5K
Top