Calculating PermutationsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/