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
_____________________________________________

Calculating Permutations


Date: 05/29/2001 at 21:36:23
From: Andrew
Subject: Permutations

I don't understand how the formula for calculating the total possible 
number of ways to choose r objects out of a total n objects works. I 
know the formula is 

         n!
p  = -----------
      p! (n-p)!


Date: 05/30/2001 at 19:29:32
From: Doctor Greenie
Subject: Re: Permutations

Hi, Andrew -

It is admirable that you are concerned with understanding why the 
formula works. I hope you are able tokeep up your interest in the 
"why" as well as the "how" - you will get much more enjoyment out of 
mathematics if you can do that.

I'm going to use the notation C(m,n) for "m choose n."  Then the 
formula for C(m,n) is

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

This is just a convenient way to write the general expression. If you 
think of a specific numerical example, the numerical value of the 
expression becomes more clear, and the "why" behind the formula 
becomes apparent.

Let's look at a specific example: C(8,3).

First, let's see what happens to the formula when we put these 
specific numbers in.

                8!        8*7*6*5*4*3*2*1       8*7*6
    C(8,3) = ------- = --------------------- = -------
              3! 5!     (3*2*1) (5*4*3*2*1)     3*2*1

One nice thing about C(m,n) is that when you actually calculate a 
value for a particular m and n, whole groups of the factors in the 
numerator and denominator always cancel, as did the factors 
(5*4*3*2*1) in this case.

Now let's think about the physical meaning of C(8,3). I have a group 
of eight objects and I'm going to choose three of them. How many ways 
can I do it? (The answer had better turn out to be the expression 
above!)

Let's first think about how many different ways I can choose three of 
the eight objects if order is important. I can choose any of the eight 
first. Then, for each of those eight choices, there would be seven 
choices for my second selection. That makes a total of 8*7 choices for 
the first two out of eight. Then, for each of those 8*7 choices for 
the first two, there would be six choices for the third. That makes a 
total of 8*7*6 different ordered ways in which I can pick three of the 
eight objects.

But mathematically "choose" has the meaning that order is not 
important (we are choosing a committee of 3 - not a president, vice 
president and secretary). So the list of 8*7*6 different orders 
contains each combination of 3 of the 8 objects several times, in 
different orders. How many times does each group of 3 occur in that 
list?  Well, any one of the three could have been chosen first. For 
each of those three choices, there are two choices for which one could 
have been chosen second, giving 3*2 ways to choose the first two of 
the three. For each of those 3*2 choices for the first two there would 
be only one choice left, for a total of 3*2*1 ways for choosing each 
particular group of three.

So our list of 8*7*6 ordered ways for choosing three objects from a 
group of eight includes each particular group of three objects 3*2*1 
times - so the number of ways of choosing three objects from eight is

    8*7*6
    -----
    3*2*1

So the formula for C(8,3) simplifies to

    8*7*6
    -----
    3*2*1

And in this expression, the "8*7*6" is the number of ordered ways I 
can pick three out of eight; while the "3*2*1" is the number of 
different orders in which any of those groups of three out of eight 
could have been chosen.

Whenever I am doing any work where I use C(m,n) frequently, I find 
that I don't think of the formula as it is formally defined. For 
example, if I run into the need for C(8,3), I don't think of

                8!        8*7*6*5*4*3*2*1       8*7*6
    C(8,3) = ------- = --------------------- = -------
              3! 5!     (3*2*1) (5*4*3*2*1)     3*2*1

Instead, I think as follows:

             3 decreasing factors, starting with 8    8*7*6
    C(8,3) = ------------------------------------- = -------
             3 decreasing factors, starting with 3    3*2*1

This way of remembering C(8,3) works better for me; it also gives a 
better picture of the meaning of the formula. You could do the same 
thing with C(m,n):

           n decreasing factors, starting with m    m(m-1)...(m-n+1)
  C(m,n) = ------------------------------------- = ------------------
           n decreasing factors, starting with n   n(n-1)...(3)(2)(1)

However, the standard form for the definition of C(m,n) is more 
compact.

For more on permutations and combinations, see the Dr. Math FAQ:

  http://mathforum.org/dr.math/faq/faq.comb.perm.html   

I hope all this helps. Thanks again for showing an interest in really 
understanding mathematics!

- Doctor Greenie, 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/