A 'permutation' of a collection of distinct objects is an arrangement of the objects (without repetition) in which the order is important. If one were to ask how many permutations there are of the letters {a,b,c,d,e}, by the basic principle of counting the answer is 5x4x3x2x1=120, since one has 5 choices for the first letter, then just 4 for the second since repetition is not allowed, and so on. There is a special mathematical symbol to denote 5x4x3x2x1, namely 5!. The exclamation point is read factorial, and it is defined for positive integers to mean that one multiplies together all the integers starting at the given integer (here 5) decreasing by 1 each time until one reaches 1. So, for example, 4!=4x3x2x1=24, 3!=3x2x1=6, 2!=2x1=2, and 1!=1. In general, n! = nx(n-1)x(n-2) . . . 3x2x1, where the dots indicate a continuation along the same pattern. (In order that the formulas derived below work in general, 0! is defined to be equal to 1.)
A problem in combinatorial theory is to determine how many total permutations are possible if one selects only a certain fixed number of objects from the collection. For example, to determine how many total permutations there are if one chooses exactly 3 letters without repetition from the letters {a,b,c,d,e}, by the basic principle of counting the answer is 5x4x3=60. One could list them as follows:
The factorial symbol can be used to come up with a simple formula for the total number of these permutations. Let nPr denote the number of permutations of n different objects when r are chosen without repetition. For example, 5P3 = 5x4x3 = 5x4x3x2x1/2x1 = 5!/2! , and 6P2 = 6x5 = 6x5x4x3x2x1/4x3x2x1 = 6!/4!. Generalizing this, the formula for nPr is nPr = n!/(n-r)!. (Note that if one chooses all n objects this reduces to the original problem of how many permutations there are of a collection of n objects. The formula gives nPn = n!/0! = n!, as it should, since we define 0! to be 1.)
A 'combination' is like a permutation, except that order is not important. For example, to determine how many ways one can choose 3 letters without repetition in which order is not important from the letters {a,b,c,d,e}, one sees that each 3 letter group in the list above can be ordered in 3P3 = 3! = 6 different ways. For example, the three letter group abc gives rise to 3! = 6 permutations, namely abc, acb, bac, bca, cab, cba. Thus to get the number of combinations one must divide the number of permutations by 3! = 6, which in this case equals 10 (abc,abd,abe,acd,ace,ade,bcd,bce,bde,cde). Let nCr denote the number of combinations of n different objects where r are chosen and order is not important. For example 5C3 = 5P3/3! = 5!/3!2! = 10, and 6C2 = 6P2/2! = 6!/2!4! = 15. Generalizing this result, the formula for nCr is nCr = [n!/(n-r)!]/r! = n!/r!(n-r)!. (Note that if one chooses all n objects there is only 1 combination. The formula gives nCn = n!/n!0! = 1, since we define 0! to be 1.)
In Powerball, Hot Lotto, and Gopher5, a certain number of balls are chosen without replacement from a container in which there are a fixed number of different balls. The order in which the balls are chosen is not important, so this is a problem where the combination formula can be used. For example, in Powerball 5 balls are chosen from a container containing 55 white balls. This can be done in 55C5 = 55!/5!50! = 55P5/5! = 55x54x53x52x51/5x4x3x2x1 = 3,478,561 ways.
In Powerball, a sixth ball is chosen from a second container containing 42 red balls. By the basic principle of counting one multiplies 55C5 by 42C1 = 3,478,561 x 42 = 146,107,962 to get the total number of possible Powerball selections.
To compute favorable ways one also uses the basic principle of counting along with the formula for combinations. For example, in Powerball, to find the number of favorable ways to come up with matching exactly 3 of the white balls, one would reason as follows: To match exactly 3 of the white balls means one must match any 3 of the five white ball numbers drawn and therefore any 2 of the 50 white ball numbers not drawn. This can be done in 5C3 x 50C2 = 5!/3!2! x 50!/2!48! = 10 x 1225 = 12,250. By the basic principle of counting, the number of ways one can match exactly 3 of the white balls and the powerball is 12,250 x 1; the number of ways one can match exactly 3 of the white balls and not the powerball is 12,250 x 41 = 502,250.