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

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
Math Forum Home || Math Library || Quick Reference || Math Forum Search