Permutation: nPr = n!/(n-r)!
n = the total number of elements in the set
r = the number of elements chosen from the set
Permutations take into account the order of the elements. Thus, {1, 2, 3, 4} is different than {2, 1, 3, 4} and so forth.
Example: You need to randomly draw 5 contest winners from a box containing 15 names. The first winner gets the largest prize with each successive winner receiving a smaller prize amount. How many ways can you select the 5 winners?
Answer: n = 15, r = 5.
15!/(15-5)! = 15!/10! = 15*14*13*12*11 = 360,360 ways.
The prize levels are different. If entry numbers 1, 2, 3, 4, and 5 are drawn, the order in which they are drawn matters. The first one to be drawn gets the biggest prize and so forth.
Theory: When you need to take n objects and put them into some arrangement, you can select any of the n objects to go into the first spot. You then have n-1 remaining objects to place into the second spot. You have n-2 remaining objects to place into the third spot, and so on. Overall, there are n*(n-1)*(n-2)*...*2*1 ways to order these objects. What if you only need r of these n objects in your arrangement? There are still n objects to select for the first spot. There are still n-1 objects for the second spot. But after you select the r-th object, you are done. So you only want to continue until you have n-r objects left. You do NOT want to arrange the n-r object because you have already arranged r objects. You want to stop after the n-r+1 object (the object right before the n-r object). How is this written?
Normally you have n*(n-1)*(n-2)*...*2*1. Now you only want n*(n-1)*(n-2)*...*(n-r+1). This is the same as n!/(n-r)! (why?)
Combination: nCr = n!/(n-r)!r!
n = the total number of elements in the set
r = the number of elements chosen from the set
Combinations do not take into account the order of the elements. Thus, {1, 2, 3, 4} is the same as {2, 1, 3, 4} and so forth.
Example: You need to randomly draw 5 contest winners from a box containing 15 names. Each winner gets the same prize amount. How many ways can you select the 5 winners?
Answer: n = 15, r = 5.
15!/(15-5)!5! = 15!/10!5! = (15*14*13*12*11)/(5*4*3*2*1) = 3,003 ways.
There are fewer ways to choose the winners because the order the winners are drawn doesn't matter anymore. Each winner gets the same prize, so whether you are drawn first or fifth it does not matter.
Theory: Same as a permutation with one extra value. We still only need to select the first r objects of the n total objects. But since order doesn't matter anymore, we need to only consider unique selections of the objects. In other words, we have to account for duplicate selections of the 5 object subgroups (from our example).
Of the original 360,360 possible arrangements, how many of them have some ordering of the elements {1, 2, 3, 4, 5}? Well there's that one. There's {1, 2, 3, 5, 4}. There's {2, 5, 4, 1, 3}. There's a lot. There are 120 ways you can take 5 elements (5! = 120) and arrange them. Of those 120 ways, we only need to consider 1 of them. It doesn't matter which one. For simplicity's sake we'll just go with the arrangement that orders them least to greatest: {1, 2, 3, 4, 5}. There are 120 ways we could select those 5 winners but we only need to consider 1 of them since they all win the same prize. Thus, we take our original equation:
n!/(n-r)!
And divide that by the number of ways we can arrange the r elements that we have chosen: r!
We get n!/(n-r)!r!
Now people can stop asking about the destroyer question #s 20 and 27.
