N Choose K Formula: Exploring the Two Equations for Finding Combinations

  • Thread starter zoxee
  • Start date
  • Tags
    Formula
In summary, the two formulas for n choose k are ## \dfrac{n(n-1)(n-2)...(n-k+1)}{k!} ## and ## \dfrac{n!}{k!(n-k)!} ##, and to get from one to the other, you expand out n! and cancel out the (n-k)! terms.
  • #1
zoxee
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:
Physics news on Phys.org
  • #2
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
zoxee said:
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
Thank you both, got it.
 
  • #5
zoxee said:
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
Ray Vickson said:
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
zoxee said:
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
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
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
 

1. What is the N Choose K formula?

The N Choose K formula, also known as the Combination formula, is a mathematical equation used to determine the number of ways to choose a subset of K items from a larger set of N items. It is represented as nCk or "n choose k", where n is the total number of items and k is the number of items being chosen.

2. How is the N Choose K formula calculated?

The N Choose K formula can be calculated using two different equations: nCk = n! / (k!(n-k)!) and nCk = (n-1)C(k-1) + (n-1)Ck. The first equation uses factorials to determine the total number of combinations, while the second equation uses the concept of Pascal's Triangle to find the value of nCk.

3. What is the purpose of the N Choose K formula?

The N Choose K formula is used in a variety of fields, including mathematics, statistics, and computer science. It helps to determine the number of possible combinations or arrangements of items, and is often used in probability calculations and in solving real-life problems involving choosing a certain number of items from a larger group.

4. What is the difference between combinations and permutations?

Combinations and permutations are both ways of arranging or choosing items from a larger set, but they differ in the order of the chosen items. Combinations do not consider the order of the chosen items, while permutations do. For example, choosing three items from a set of four would result in four different combinations (ABC, ABD, ACD, and BCD) but would result in 24 different permutations (ABC, ACB, BAC, BCA, CAB, CBA, etc.).

5. Can the N Choose K formula be used for any number of items and choices?

Yes, the N Choose K formula can be used for any number of items and choices. However, it is important to note that the values of n and k must be positive integers, and n must be greater than or equal to k. Additionally, for very large values of n and k, it may be more efficient to use a calculator or computer program to calculate the formula.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
3
Views
239
  • Precalculus Mathematics Homework Help
Replies
6
Views
827
  • Precalculus Mathematics Homework Help
Replies
6
Views
690
  • Precalculus Mathematics Homework Help
Replies
8
Views
1K
  • Precalculus Mathematics Homework Help
Replies
23
Views
3K
  • Precalculus Mathematics Homework Help
Replies
5
Views
953
  • Precalculus Mathematics Homework Help
Replies
5
Views
970
  • Precalculus Mathematics Homework Help
Replies
8
Views
1K
  • Precalculus Mathematics Homework Help
Replies
34
Views
2K
  • Advanced Physics Homework Help
Replies
2
Views
1K
Back
Top