Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/