Associated Topics || Dr. Math Home || Search Dr. Math

### Permutations and Combinations: Deriving Formulae

```
Date: 06/18/98 at 22:14:24
From: Lim Yoke Kuang
Subject: Combinations

I have been trying very hard to figure out how to arrive at a formula
for calculating combinations, but in vain. The formula is

n!/r!(n-r)!

which calculates the number of times where r objects can be chosen
from n objects.

I hope that you can send me a reply. Thank you very much!
```

```
Date: 06/19/98 at 07:52:58
From: Doctor Anthony
Subject: Re: Combinations

The mathematics we use in calculating the number of combinations of,
say, 6 things from 49 comes under the general heading of Permutations
and Combinations. Most textbooks in intermediate algebra or in basic
probability will have chapters covering this topic, and you should
consult such a book to find the proofs of the formulae employed. They
are not difficult to understand and I will give a brief outline below.

PERMUTATIONS

If we have, say, 10 different objects (e.g. letters a - j of the
alphabet), how many different 'words' could be made using 4 of the
letters? In this context we simply want 4 letters, such as bghc; they
do not need to spell a known English word. But the ORDER of the
letters does matter, so hgcb is different from bghc.

With 10 letters to choose from we can select the first letter in
10 ways. We are now down to 9 letters, so the second letter can be
chosen in 9 ways, then the third letter in 8 ways, and the 4th letter
in 7 ways.

The total number of ways of arranging 4 letters chosen from 10 is
10 x 9 x 8 x 7 = 5040.

We use the symbol  nPr to represent the number of ways of arranging r
things chosen from n different things, so here we have 10P4 = 5040

In ascii notation this is sometimes written P(n,r), so for this
problem we have P(10,4) = 5040

We can also express P(10,4) using factorials.

Factorial notation uses the exclamation mark ! to show that it is a
factorial, where for example

5! = 5 x 4 x 3 x 2 x 1 = 120
10! = 10 x 9 x 8 x ... x 3 x 2 x 1 = 3628800

You will notice that factorials get very big very quickly.

10!     10 x 9 x 8 x 7 x 6!
Using this notation  P(10,4) = -----  = -------------------  =  5040
6!             6!

n!
The general formula for  P(n,r) is   ------
(n-r)!

COMBINATIONS

These are closely allied to permutations except that the order does
not matter. For example in our problem of 4 letters chosen from 10
letters, the 4 letters hgcb are the SAME combination as bghc.

To find the number of combinations we use the fact that the number of
permutations of 4 letters from 10 is P(10,4), but now EVERY
permutation can be rearranged in 4! = 24 ways without giving rise to a
different combination. So the number P(10,4) is too large by a factor
of 4! when we calculate the number of combinations. This leads to the
following formula for the number of combinations:

10!
C(10,4) = -------  =  210
4! 6!

The general formula for the number of combinations of r things chosen
from n different things is

n!
C(n,r) = ---------
r!(n-r)!

We can now answer the question you started with. How many ways can 6
numbers be chosen from 49 numbers? (The order you choose the numbers
does not matter).

Here we use the combination formula and get:

49!
C(49,6) = ---------  =  13,983,816
6! 43!

This is not the 32 million that you quoted.

The second question was the number of ways of choosing 10 numbers from
35. This is given by:

35!
C(35,10) = ---------   =  183,579,396
10! 25!

So now we are up to nearly 184 million possible combinations.

-Doctor Anthony,  The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search