# How to calculate winning odds in Powerball

Powerball is a lottery game available for play in 44 states in the United States and in the District of Columbia, Puerto Rico and the US Virgin Islands. It is a “mega” lottery because of the usually huge jackpot. As of the writing of this post, the estimated jackpot is $113 million (see the below picture). The largest Powerball jackpot is$1.59 billion on January 13, 2016 (this was also the largest in US lottery history). The average Powerball jackpot is $62.71 million. Recent jackpots had been in the range of hundreds of million dollars. With such large jackpots, it is not surprising that Powerball is a popular lottery game, especially when the impending jackpot is in the hundreds of millions dollars. Bear in mind that the odds of winning the jackpot are slim: 1 in 292,201,338, i.e. one in over 292 million. This post is to demonstrate how to mathematically derive the winning odds of the jackpot and other smaller prizes of Powerball (the first objective). Calculating the odds is a great math lesson. It is equally interesting and equally important to make sense of the large numbers in the small winning odds. The second objective is to focus on the dim prospect of Powerball players as told by the mathematical odds. Figure 1 – Powerball Results on April 26, 2017 ___________________________________________________________________________ The Game of Powerball This is how the game is played. In a Powerball playslip, a player picks 5 numbers from 1 through 69 and 1 number from 1 through 26 (this is the Powerball number). Drawings are held Wednesday and Saturday evenings at 10:59 p.m. Eastern Time. In each drawing, five balls are drawn from a drum with 69 white balls (labeled 1 through 69) and one ball is drawn from a drum with 26 red balls (labeled 1 through 26). Figure 1 above shows that the winning numbers on April 26, 2017 are 1, 15, 18, 26 and 51 (white) and 26 (red). The winnings are determined by whether the numbers in the playslip match the balls drawn at the Powerball drawing. The grand prize is awarded to the player (or players) whose ticket matches all of the numbers on the five chosen white balls and the one chosen red ball. Smaller prizes are awarded to players whose tickets match fewer number of white balls with or without the red ball. The following table shows the levels of prizes and the odds. These Powerball payout rules had been in place since October 7, 2015. Figure 2 – Powerball Prizes and Odds $\bold S \bold o \bold u \bold r \bold c \bold e: \bold w \bold w \bold w. \bold p \bold o \bold w \bold e \bold r \bold b \bold a \bold l \bold l. \bold c \bold o \bold m$ As shown by the table, the prizes are for scenarios ranging from matching zero white balls to all 5 of the white balls (with or without the match of the red ball). Of course, matching all 6 balls would lead to the grand prize. Matching just the 5 white balls without the red ball would be the fixed prize of$1 million. Matching any 4 of the white balls plus the red ball would lead to the prize of $50,000. The rest of the prizes are for practically insignificant amounts. Each Powerball ticket is$2. For an additional $1 per game, a player may activate the Power Play option. When this option is activated, the lower prizes that are$50,000 or less are multiplied by a factor from 1 up to 5 or 10 (10x is available when the jackpot is under $150 million). With the Power Play Option, the prize for the “5 white balls and no red ball” match is increased to$2 million. That is, the “5 + 0” prize is doubled under the Power Play Option. For further information on Powerball, see the Wikipedia entry.

The odds represented in the above table are essentially winning probabilities for a Powerball player (per $2 bet). The odds for the grand prize is 1 in 292,201,338. So the probability of winning the grand prize with one ticket is 1 / 292,201,338, which of course is essentially zero. This probability is essentially this statement: out of 292,201,338 different possible Powerball combinations and only one of them is the winning combination. The odds for the$1 million prize is 1 in 11,688,353.52, about 1 in 11 million (still very slim odds). So the probability of winning $1 million with one ticket is 1 / 11,688,353.52, which is also essentially zero. Note that 1 / 11,688,353.52 is the same as 25 / 292,201,338. This last probability is the statement: out of 292,201,338 different possible Powerball combinations, only 25 of them are winning (i.e. matching all 5 white balls without the matching the red Powerball number). Thus calculating the odds for Powerball (or any other lottery game for that matter) is about counting correctly the number of possible lottery ticket combinations (the denominator) and counting the number of winning tickets (the numerator). So this is a counting exercise. In the area of mathematics called combinatorics, which at the elementary level concerns with the counting of number of ways objects can be chosen from a set (a set of balls in the case of lottery). Several previous posts of this blog are devoted to this subject. We will reference them when necessary. However, we strive to make the discussion here as self contained as possible. ___________________________________________________________________________ Using a Toy Lottery As indicated above, there are 292,201,338 different possible Powerball tickets. Out of these, there are 25 possible winning pickets for the$1 million prize. Of the 292,201,338 possible tickets, there are 320 possible winning tickets for the $50,000 prize. Instead of attacking these problems head on, we use a “toy” lottery to illustrate the idea. Any reader who feels that such introduction is not needed can skip to the next section. Based on the last paragraph in the preceding section, the winning probability is the number of possible ways to win over the number of possible “tickets.” Probability of winning = $\displaystyle \frac{\text{the number of winning numbers}}{\text{the total number of possible lottery numbers}}$ For example, if 40 tickets are sold in a raffle and only one of them is the winner, then the odds of winning would be 1 in 40. The probability of winning would be 1 / 40 = 0.025 (2.5% chance). If two of the 40 tickets are winners, then the odds are 1 in 20. The probability of winning would then be 2 / 40 = 0.05 (5% chance). Though the Powerball calculation is based on this simple idea, there are subtle points that need to be addressed in order to fully understand the calculation. So we take the approach of using a toy lottery. Let’s call the game “toy Powerball.” The player picks two numbers from 5 white balls (labeled 1 through 5) and picks one number from 4 red balls (labeled 1 through 4). The prizes are: • grand prize (match all 2 white balls and 1 red ball), •$100 prize (match 2 white balls and not matching the red ball),
• $10 prize (match 1 white ball and the red ball). How many different possible tickets are there? Since there are two drawings (one for the white ball and one for the red ball), we need to count them separately and multiply the results. Since there are only 5 white balls, we can actually count the number of ways to choose 2 balls out of 5 white balls. 1, 2 1, 3 1, 4 1, 5 2, 3 2, 4 2, 5 3, 4 3, 5 4, 5 There are obviously 4 ways to choose one ball out of 4 red balls. So the total number of different possible tickets are 10 x 4 = 40. This is based on the so called multiplication principle – if one event can occur in $M$ ways and another event can occur, independent of the first event, in $N$ ways, then the two events together can occur in $M \times N$ ways. The multiplication principle, discussed here, will be a great help in calculating the odds. For example, the first event is the choosing of the white balls and the second event is the choosing of the red balls. This idea can be used to find the number of possibilities in both the denominator and the numerator. There is only one possible winning ticket for the grand prize (of course, if two people pick the same winning combination, they will split the prize). So the odds for winning the grand prize is 1 in 40. The probability of winning the grand prize is 1 / 40 = 0.025 (2.5%). Is there a way to calculate the number of ways to choose two balls out of 5 white balls (labeled 1 through 5) without writing down all possibilities? This will be key to the Powerball calculation. There are two ways. One is an intuitive approach using the multiplication principle and the other is to use a formula for combination. The first idea. Choosing two numbers is like filling two spots with numbers. In this case, the first spot has 5 choices and the second spot has 4 choices after the first spot is filled. This gives a total of 5 x 4 = 20. But 20 is an over count. For example, the result 3-2 (first number is 3 and the second number is 2) is actually the same as 2-3 as far as the lottery is concerned. So each 2-number combination appears twice in the count of 20. Thus dividing by 2 gives 20 / 2 = 10. The other way is via a formula for combination. In the toy Powerball example, we need to choose 2 balls out of 5 balls. The following is the calculation. $\displaystyle \frac{5!}{2! \ 3!}=\frac{120}{2 \times 6}=10$ Let’s unpack this calculation. The notation 5!, read 5 factorial, is 5 x 4 x 3 x 2 x 1 = 120, in other words, obtained by multiplying together 5 and all the positive integers below 5. Thus 6! = 6 x 5 x 4 x 3 x 2 x 1 = 6 x 120 = 720. In general, whenever $n$ is a positive integer, $n!$, read $n$ factorial, is obtained by multiplying $n$ and all the positive integers below $n$. To make the calculation works out, we define 0! = 1. Is there any natural interpretation of factorial? For example, 5! is the number ways to arrange 5 people in a row for a group photo. Five people are to be assigned into 5 spots. There are 5 possibilities for the first spot, 4 possibilities for the second spot after the first person is chosen and so on. By the multiplication principle, the total number of ways to do this would be 5 x 4 x 3 x 2 x 1. In general $n!$ is the number of ordered arrangements of $n$ objects. Thus the number of ways to choose 2 balls out of 5 balls is 10 (also the number of ways to choose two people out of 5 to form a committee of 2, the number of ways to choose 2 students out of 5 for awards, or the number of ways to choose 2 ice cream flavors out of 5 – the possibility is endless). The notation for “choose 2 from 5” is $\binom{5}{2}$. The top number in this notation is the total number of objects to choose from and the bottom number is the number of objects to be chosen. In general, the number of ways to choose $r$ objects out of $n$ objects is $\displaystyle \binom{n}{k}=\frac{n!}{r! \ (n-r)!}$ The number $\binom{n}{r}$ is called the number of possible combinations of $n$ objects chosen $r$ at a time. Other notations include $_nC_r$ and $C(n,r)$. Regardless the notations, it is the number of ways to choose $r$ objects from a set of $n$ objects or the number of different groups of size $r$ that can be chosen from a set of $n$ distinct objects. Many calculators have a function for the number $\binom{n}{r}$ (in a calculator the notation is probably $_nC_r$). If it is to be calculated by hand, bear in mind that $n!$, factorial of the total number of object, is in the numerator and the two factorials in the denominator are $r!$ and $(n-r)!$ where $r$ is the number of objects to be chosen. Note that the sum of $r$ and $n-r$ is $n$. For more information about how to calculate combination, see here and the summary section here. Let’s look at the second prize in toy Powerball – match 2 white balls and no match for red ball. As example, let’s say the winning numbers are 1 and 3 (white) and 2 (red). How many 3-number combinations satisfy the winning criteria for this prize – matching two white numbers and not the red number? There is still only one way to match the two white numbers. But there are 3 ways to not match the red winning numbers (the non-winning red numbers would be 1, 3, and 4). The number of possible winning tickets would be 1 x 3 = 3. So the odds for winning the$100 prize are 3 in 40. The probability of winning the $100 prize is 3 / 40 = 0.075 (7.5%). The third prize is$10 won by matching 1 white ball and 1 red ball. Again, using the example of winning numbers of 1 and 3 (white) and 2 (red), how many 3-number combinations satisfy the winning criteria for this prize – matching 1 white number and the red number? Remember that the player of the game chooses 2 white numbers and 1 red number. Since there is only 1 correct match for white number, there are 1 winning white number and 1 non-winning white number in the ticket. There are two ways to match 1 winning white number (1 or 3) and there are 3 ways to match 1 non-winning white number (2, 4 and 5). Of course, there is only one way to match the winning red number. The number of possible winning tickets would be 2 x 3 x 1 = 6 (by the multiplication principle again). This observation will be crucial in understanding the Powerball calculation below.

So the odds for winning the $10 prize are 6 in 40. The probability of winning would be 6 / 40 = 0.15 (15%). ___________________________________________________________________________ Back to Powerball The winning probability of a prize in a lottery would be the fraction of all of the possible lottery numbers which count as winning. In other words, the winning probability would be a fraction with the denominator being the total number of possible number combinations that can be picked by the lottery players and the numerator being the number of possible winning combinations. So the denominator is always fixed for a given lottery. The numerator would vary depending on the prize. The bigger the prize, the smaller the numerator (the harder it is to win). For the Powerball game uses a 6-number combination (5 white numbers + 1 red number). the 5 white numbers are chosen out of 69 numbers and the 1 red number is chosen out of 26 numbers. So based on the discussion in the preceding section, the total number of possible 6-number combinations would be: Total Number of Possible Powerball Combinations $\displaystyle \binom{69}{5} \cdot \binom{26}{1}=\text{11,238,513} \times 26=\text{292,201,338}$ There are $\binom{69}{5}$ many possible 5-number sets that can be picked from 69 numbers. There are over 11 millions ways to match the 5 winning white balls. There are $\binom{26}{1}$ = 26 possible ways to pick one number from 26 numbers. By the multiplication principle, the product of these numbers would be the total number of possible Powerball combinations. For the winning probability of any Powerball prize, the denominator would be 292,201,338, which is a staggering number. To help with understanding what should go into the numerator, let’s use the latest winning combination: 1, 15, 18, 26 and 51 (white balls) and 26 (red ball), drawn on April 26, 2017 (shown in Figure 1 above). So all the winning calculations below are based on this example. The number that goes into the numerator would be the number of tickets matching some or all of the white numbers with or without matching the red number depending on the rules. Let’s consider the prizes one by one. Match 5 white balls + 1 red ball (grand prize) There is only winning combination. So the winning probability is 1 over 292,201,338. The winning odds would be 1 in 292,201,338. Match 5 white balls + no red ball ($1,000,000)

Probability of winning = $\displaystyle \frac{\displaystyle \binom{5}{5} \cdot \binom{1}{0} \cdot \binom{25}{1}}{292201338}=\frac{1 \cdot 25}{292201338}=\frac{25}{292201338}$

The relevant question here is: how many ticket combinations are that that match all 5 winning white numbers and that do match the 1 red winning number? There is only one way to match all 5 white numbers 1, 15, 18, 26 and 51 (as in the grand prize). There are 25 ways to not match the winning red number 26 (1 through 25). So the numerator is 25. So the odds for winning $1 million are 25 in 292,201,338 or 1 in 11,688,053.52 (1 in over 11 million). Match 4 white balls + 1 red ball ($50,000)

Probability of winning = $\displaystyle \frac{\displaystyle \binom{5}{4} \cdot \binom{64}{1} \cdot \binom{1}{1} \cdot \binom{25}{0}}{292201338}=\frac{5 \cdot 64}{292201338}=\frac{320}{292201338}$

To win, a player needs to match 4 of the white numbers. To count all the winning combinations, choose 4 numbers from the 5 winning white numbers and choose 1 number from the 64 non-winning white numbers Recall that the ticket has 5 white numbers. If only 4 of them match the winning numbers, then one of the white numbers on the ticket must from a non-winning white number.

Furthermore, choose 1 number from the 1 winning red number and 0 numbers from the 25 non-winning red numbers. This observation explains what appear in the numerator. Then the odds for winning the $50,000 prize are 320 in 292,201,338 or 1 in 913,129.18. Match 4 white balls + no red ball ($100)

Probability of winning = $\displaystyle \frac{\displaystyle \binom{5}{4} \cdot \binom{64}{1} \cdot \binom{1}{0} \cdot \binom{25}{1}}{292201338}=\frac{5 \cdot 64 \cdot 25}{292201338}=\frac{8000}{292201338}$

Without the red ball match, there are more ways to win (25 more to be precise). To count the number of winning tickets, choose 4 from the 5 winning white numbers, choose 1 from the 64 non-winning white numbers, choose 0 from the 1 winning red number and choose 1 from the 25 non-winning red numbers. Doing this gives 8,000. Then the odds for winning the $100 prize are 8,000 in 292,201,338 or 1 in 36,525.17. Match 3 white balls + 1 red ball ($100)

Probability of winning = $\displaystyle \frac{\displaystyle \binom{5}{3} \cdot \binom{64}{2} \cdot \binom{1}{1} \cdot \binom{25}{0}}{292201338}=\frac{10 \cdot 2016 \cdot 1}{292201338}=\frac{20160}{292201338}$

To count the number of winning tickets, choose 3 from the 5 winning white numbers, choose 2 from the 64 non-winning white numbers, choose 1 from the 1 winning red number and choose 0 from the 25 non-winning red numbers. Doing this gives 20,160. Then the odds for winning the second $100 prize are 20,160 in 292,201,338 or 1 in 14,494.11. Match 3 white balls + no red ball ($7)

Probability of winning = $\displaystyle \frac{\displaystyle \binom{5}{3} \cdot \binom{64}{2} \cdot \binom{1}{0} \cdot \binom{25}{1}}{292201338}=\frac{10 \cdot 2016 \cdot 25}{292201338}=\frac{504000}{292201338}$

Let’s use the latest winning numbers 1, 15, 18, 26 and 51 (white balls) and 26 (red ball) to illustrate. How many ticket combinations would satisfy this criteria: match 3 numbers from 1, 15, 18, 26 and 51 (white balls) and not match the winning red number 25? The answer is the number of ways to choose 3 from 1, 15, 18, 26 and 51, choose 2 from the other 64 white numbers, choose 0 from 1 winning red number (26) and choose 1 from 25 non-winning red numbers. This explains what is in the numerator, which is 504,000. Then the odds for winning the first $7 prize are 504,000 in 292,201,338 or 1 in 579.76. Match 2 white balls + 1 red ball ($7)

Probability of winning = $\displaystyle \frac{\displaystyle \binom{5}{2} \cdot \binom{64}{3} \cdot \binom{1}{1} \cdot \binom{25}{0}}{292201338}=\frac{10 \cdot 41664 \cdot 1}{292201338}=\frac{416640}{292201338}$

Using similar idea to set up the numerator, the numerator is 416,640. Then the odds for winning the second $7 prize are 416,640 in 292,201,338 or 1 in 701.33. Match 1 white ball + 1 red ball ($4)

Probability of winning = $\displaystyle \frac{\displaystyle \binom{5}{1} \cdot \binom{64}{4} \cdot \binom{1}{1} \cdot \binom{25}{0}}{292201338}=\frac{5 \cdot 635376 \cdot 1}{292201338}=\frac{3176880}{292201338}$

As discussed earlier, when the match of the white balls is partial, the white numbers that do not match the winning white numbers must come from the 64 non-winning numbers. So we choose 1 from 5 winning white numbers and choose 4 from 64 non-winning white numbers. There is only one way to pick the winning red number. The numerator is 3,176,880. Then the odds for winning the first $4 prize are 3,176,880 in 292,201,338 or 1 in 91.98. Match no white ball + 1 red ball ($4)

Probability of winning = $\displaystyle \frac{\displaystyle \binom{5}{0} \cdot \binom{64}{5} \cdot \binom{1}{1} \cdot \binom{25}{0}}{292201338}=\frac{1 \cdot 7624512 \cdot 1}{292201338}=\frac{7624512}{292201338}$

The numerator is 7,624,512. Then the odds for winning the second $4 prize are 7,624,512 in 292,201,338 or 1 in 38.32. The overall odds of winning a prize The total number of possible 6-number combinations that result in a prize is obtained by summing all the numerators in the above calculation of odds. There is a total of 11,750,538 many possible prizes. The following table shows the breakdown. Number of Possible Prizes $\begin{array}{rrrrrrr} \text{Match} & \text{ } & \text{Prize} & \text{ } & \text{Odds} & \text{ } & \text{Number of Prizes}\\ \text{ } & \text{ } \\ \text{5 white, 1 red} & \text{ } & \text{Grand Prize} & \text{ } & \text{1 in 292,201,338} & \text{ } & 1\\ \text{5 white, no red} & \text{ } & \ \text{1 million} & \text{ } & \text{1 in 11,688,053.52} & \text{ } & 25\\ \text{4 white, 1 red} & \text{ } & \ \text{50,000} & \text{ } & \text{1 in 913,129.18} & \text{ } & 320\\ \text{4 white, no red} & \text{ } & \ 100 & \text{ } & \text{1 in 36,525.17} & \text{ } & \text{8,000}\\ \text{3 white, 1 red} & \text{ } & \ 100 & \text{ } & \text{1 in 14,494.11} & \text{ } & \text{20,160}\\ \text{3 white, no red} & \text{ } & \ 7 & \text{ } & \text{1 in 579.76} & \text{ } & \text{504,000}\\ \text{2 white, 1 red} & \text{ } & \ 7 & \text{ } & \text{1 in 701.33} & \text{ } & \text{416,640}\\ \text{1 white, 1 red} & \text{ } & \ 4 & \text{ } & \text{1 in 91.98} & \text{ } & \text{3,176,880}\\ \text{no white, 1 red} & \text{ } & \ 4 & \text{ } & \text{1 in 38.32} & \text{ } & \text{7,624,512}\\ \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ }\\ \text{ } & \text{ } & \text{Any Prize} & \text{ } & \text{1 in 24.87} & \text{ } & 11,750,538 \end{array}$ The odds of winning any prize would be 11,750,538 in 292,201,338, or 1 in 24.87. It ought to be mentioned that the last column in the table is only for the number of potential prizes in a category (they are number of possible winning combinations). A prize is awarded only when someone purchased the winning combination. For example, on April 26, 2017, no one won the grand prize since no one had purchased the winning numbers of 1, 15, 18, 26, and 51 and 26. No one had won the$2 million prize for match 5 power play. However, there were three winners for the match 5 (they did not pay for the extra power play option). There are 25 possible winning combinations but only three were won. Figure 1 also shows that there were 592,253 winners on that day. Potentially, there could be 11,750,538 (or more) winners in each drawing.

Remarks on Calculations
First, we emphasize again the point that has been made several times already. The smaller prizes only require partial matching of white numbers with or without matching of the red number. The matching of white numbers must account for winning and non-winning numbers. For example, if the prize requires the matching of 3 white numbers, then we need to count 3 numbers from the 5 winning white numbers and 2 numbers from 64 non-winning white numbers. Hence $\binom{5}{3} \times \binom{64}{2}$. Recall that to play Powerball, the player chooses 5 numbers from the 69 white balls. If the player matches only 3 winning white balls, the other two white numbers chosen by the player must come from the 64 non-winning white balls.

The odds for the last prize (matching the red number only) are not 1 in 26. This is a common misconception. There are only 26 red balls. So matching the red ball must have a 1 in 26 chance. However, we cannot ignore the white balls! The fact that only the red ball is matching means that the 5 white numbers chosen by the player must come from the 64 non-winning white numbers. So the correct value to go into the numerator is $\binom{5}{0} \times \binom{64}{5}$.

___________________________________________________________________________

Do You Feel Lucky Today?

The odds for winning the Powerball jackpot are mathematically zero (being 1 in 292 millions). The entire population of the United States is 321.4 millions in 2015, with 248 millions of them age 18 or over. If every adult in the U.S. purchases a Powerball ticket, it is still possible that there will be no winner of the grand prize (but there could be a few $1 million winners). To get a sense of how big the number 292 million is, look at this piece from WSJ. The piece strives to illustrate how vast a quantity 292,201,338 is. Just to scroll the page over that many dots is a near impossible task. One thing is for sure. With no winners of jackpot in a several drawings in a row, the excitement for Powerball is turned into a frenzy. In fact, the last revision of the Powerball rules in 2015 made winning of the jackpot much less likely. As a result the jackpot usually keeps building until it reaches hundreds of millions range or the 1 billion range. The rules were designed to rachet up the excitement and as a result driving up sales (discussed in this piece from Washington Post). Playing Powerball is an excellent entertainment. With a$2 admission price, you can dream and fantasize for a few days. Once a week habit would be about $100 a year in entertainment cost. Regular customers of Starbucks would spend more than that amount. Of the regular lottery players, roughly the top 5% spend a few thousand dollars a year (a hundred thousand dollars on average in their lifetime, assuming no interest) for an illusive chance to win$1 million or more. What if these regular players invest the money elsewhere?

If they invest the money instead on a conservative fund earning 2% a year, they would accumulate an nest egg of hundreds of thousands of dollars. Assuming a rate of returns at 2% a year, investing $3,000 a year would yield approximately$185,000. In fact, if they invest in a broad base stock market index (e.g. S&P 500 index), they would do even better in the long run. The long run historical S&P 500 returns are around 10% a year (7% after inflation). Assuming a rate of returns at 7% a year, investing $3,000 a year would yield around$640,000!

Even in the rare chance that someone wins $1 million, the winning is taxed and would be greatly reduced, e.g. the winning could be$500,000 after tax. Thus the rates of return of a lifetime investment in playing lottery are not as great as people imagine. Without winning, the lifetime lottery investment of a few thousands dollars a year would be money going down the drain. For a more detailed discussion, see this piece from Washington Post.

The calculation of the Powerball winning odds is a great math lesson. Rather than looking at the winning odds, perhaps it is more instructive to look at losing odds. The odds for not winning the Powerball grand prize (per $2 bet) are 292,201,337 to 292,201,338, which are essentially 1 in 1. ___________________________________________________________________________ $\copyright$ 2017 – Dan Ma # Multinomial coefficients This is the fourth post in a series of posts on combinatorial analysis. The post is opened with the following problem. This post builds on the previous post on binomial coefficients. Figure 1 – three choices for lunch Multinomial Lunch Problem Each of the twelve people have 3 choices for lunch – McDonald, Burger King and IN-N-OUT, all fast food restaurants. The choice for each person is independent of the choices of the other diners. 1. In how many ways can the lunch choices for this 12-person group be made? 2. In how many ways can the lunch choices for this 12-person group be made in such a way that 3 people choose McDonald, 4 people choose Burger King and 5 people choose IN-N-OUT? 3. In how many ways can the lunch choices for this 12-person group be made in such a way that 3 people choose one restaurant, 4 people choose another restaurant and 5 people choose the remaining restaurant? The previous posts on combinatorial analysis are: binomial coefficients, combination and permutation and multiplication principle. ___________________________________________________________________________ Multinomial Coefficients The problem for lunch choices is a multinomial coefficient problem. The second question in the problem is equivalent to any one of the following question. 1. How many ways can a set of 12 distinct objects be divided into 3 subgroups, one consisting of 3 objects, one consisting of 4 objects and one consisting of 5 objects? 2. How many different 12-letter strings are there consisting of 3 M’s, 4 B’s and 5 I’s? 3. Suppose each of the questions in a 12-question multiple choice test has three choices (M, D and I). A student chooses the answers by pure guessing. How many of the possible test answers consist of 3 M’s, 4 B’s and 5 I’s? 4. How many ways can 12 people be assigned to 3 committees such that one committee consists of 3 people, one committee consists of 4 people and one committee consists of 5 people? Assume that each person is assigned to only one committee. 5. An urn contains three letters M, B and I. Randomly sample 12 letters from the urn with replacement. What is the number of sample results that consist of 3 M’s, 4 B’s and 5 I’s? The first question is basically the definition of multinomial coefficient. It is the total number of ways to divide a set of objects into several subsets such that each subset is of a pre-determined size. In the second question, the objects are the 12 positions in the letter strings. In the third question, the objects to be divided are the 12 multiple choice questions. In the fourth question, the objects to be divided are the 12 people to be assigned into committees. The fifth question is from a random sampling perspective. In any of the question, the dividing can be thought of as a choice (or decision) for each object. For each of the 12 objects, should the object be put into group 1, group 2 or group 3 (or should choice 1 be taken, choice 2 be taken, choice 3 be taken)? In the lunch problem, each diner has 3 choices. The choices in their totality would be viewed as the results from a random sampling of the population of 3. The answer to any of the above questions is a multinomial coefficient. Multinomial Coefficient If $n_1+n_2+\cdots+n_k=n$, the notation for the multinomial coefficient is $\displaystyle \binom{n}{n_1,n_2,\cdots,n_k}$ and is defined by $\displaystyle \binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{n_1! n_2! \cdots n_k!}$. The multinomial coefficient is the number of ways a set of $n$ distinct objects can be divided into $k$ subsets, one of which consists of $n_1$ objects, one of which consists of $n_2$ objects, …., one of which consists of $n_k$ objects. It is clear that multinomial coefficients are a generalization of binomial coefficients. Instead of having to choose from one of two choices in each random selection, there are multiple choices to choose from. Even the notation $\displaystyle \binom{n}{n_1,n_2,\cdots,n_k}$ is a generalization of the notation $\displaystyle \binom{n}{n_1}$, the notation for binomial coefficients. Note that $\displaystyle \binom{n}{n_1,n-n_1}=\binom{n}{n_1}$. ___________________________________________________________________________ Multinomial Lunch Problem Viewing the lunch choices as random sampling (each diner randomly chooses from M, B and I), there are $3^{12}=$ 531,441 many ways can the lunch choices be made for the whole 12-person group. This count contains all the possible choices including possibilities that some restaurant is not chosen. The following is one possible outcome that fall under question 2. B-M-B-I-I-M-B-B-M-I-I-I The above string shows that the first person chooses Burger King, the second person chooses McDonald, the third person chooses Burger King and so on. How many other strings are like this one in the sense that there are 3 M’s, 4 B’s and 5 I’s? This would be a multinomial coefficient. $\displaystyle \frac{12!}{3! \ 4! \ 5!}=\frac{12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1 \cdot 4 \cdot 3 \cdot 2 \cdot 1}=\text{27,720}$ The answer to the third question is more than 27,720. For example, there could be three diners choosing IN-N-OUT, 4 diners choosing Burger King and 5 diners choosing McDonald. In other words, we need to apply multinomial coefficient on the three positions (three restaurants). There are 6 ways to divide 3 positions resulting in three subsets with one each since $\frac{3!}{1! \ 1! \ 1!}=6$. Then there are 6 x 27,720 = 166,320 ways for 12 diners making choices so that 3 of them go to one place, 4 of them go to another place and five of them go to the remaining place. This is an example of the double use of the multinomial coefficients – the first application is on dividing the objects into subgroups and the second application on the dividing the subgroups. The following example gives another illustration. Example 1 A fair die is rolled 15 times. How many of the outcomes consist of four 2’s, five 3’s and six 4’s? How many of the outcomes consist of four of one face, five of another face and six of another face (different from the other two faces)? The first question is a straight application of one multinomial coefficient. $\displaystyle \frac{15!}{4! \ 5! \ 6!}=\frac{15 \cdot 14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7}{4 \cdot 3 \cdot 2 \cdot 1 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}=\text{630,630}$ To understand the second question, consider the notation (0, 4, 5, 6, 0, 0), which means that there are zero 1’s, four 2’s, five 3’s, six 4’s, zero 5’s and zero 6’s from rolling the die 15 times. Basically it shows how many rolls fall into each position (face). Now we are interested in counting other outcomes that have 4, 5 and 6 of another 3 positions. Basically we are trying to divide 6 positions into four groups, one groups with 3 positions that do not appear in the 15 rolls, one groups with one position that appear 4 times, one group with one position that appear 5 times, and one group with one position that appears 6 times. The following shows how many ways to divide the 6 positions. $\displaystyle \frac{6!}{3! \ 1! \ 1! \ 1!}=120$ For each of the 120 times, there are 630,630 outcomes. Thus the answer to the second question is 120 x 630,630 = 75,675,600. $\square$ ___________________________________________________________________________ Multinomial Sampling We now explore the random sampling angle of multinomial coefficients. To make it easier to follow, we continue to use the Multinomial Lunch Problem. The problem, as discussed above, is like sampling 12 times with replacement from an urn with 3 letters M, B and I. Each of the 12 random selections has 3 outcomes. Thus the experiment in total has $3^{12}$ = 531,441 outcomes, each of which can be written as a string of 12 letters. Three examples: B-M-B-I-I-M-B-B-M-I-I-I I-M-M-I-M-M-M-I-M-I-I-M M-M-M-M-M-M-M-M-M-M-M-M These three strings can be called ordered samples for the experiment of randomly selecting from the urn 12 times with replacement. These display the results of each draw sequentially. We can also use unordered samples, which do not contain the orders but contain the number of times each letter is drawn. For the first string, the unordered sample would be (3, 4, 5) where the first number is the number of people choosing McDonald, the second number is the number of people choosing Burger King and the third number is the number of people choosing IN-N-OUT. For the second string, the unordered sample would be (7, 0, 5). For the third, everyone goes to McDonald and so it is (12, 0, 0). Note that (3, 4, 5) is called an unordered sample because it does not tell us the order of the chosen letters. It only tells us how many times each letter is chosen. The number of ordered samples resulting in an unordered sample would be precisely the multinomial coefficient. For the unordered sample (3, 4, 5), there would be $\displaystyle \frac{12!}{3! \ 4! \ 5!}=\frac{12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{3 \cdot 2 \cdot 1 \cdot 4 \cdot 3 \cdot 2 \cdot 1}=\text{27,720}$ many ordered samples. In randomly selecting letters 12 times with replacement from an urn containing the letters M, B and I, how many unordered samples are there? To answer this question, it is helpful to look at unordered samples using a star-and-bar diagram. The star-and-bar diagrams for above three unordered samples are: * * * | * * * * | * * * * * * * * * * * * | $\text{ }$ | * * * * * * * * * * * * * * * * * | $\text{ }$ | $\text{ }$ In the random experiment in question, a star-and-bar diagram has 12 stars, representing the 12 letters selected, and 2 bars, creating three spaces for the three letters M, B and I. In each star-and-bar diagram, there are 12 + 2 = 14 positions, 12 of which are for the stars and the remaining 2 positions are for the bars. In other words, each of the 14 positions can be either a star or a bar. Thus star-and-bar diagrams are the results of a binomial experiment. How many possible star-and-bar diagrams? There are $\displaystyle \binom{12+2}{11}=\binom{14}{11}=\binom{14}{2}=364$ many different diagrams. Thus there are 364 many unordered samples from drawing letters 12 times from an urn containing the letters M, B and I. A related question is: how many unordered samples are there in this experiments such that each letter is selected at least once? This means that each space in the star-and-bar diagram has at least one star. Then the remaining 12 – 3 = 9 stars will have to be distributed in the three spaces. There are $\displaystyle \binom{9+2}{9}=\binom{11}{9}=55$ unordered samples in which each letter is chosen at least once. There is another way to interpret the unordered samples. What is the total number of non-negative integer solutions to the equation $x + y + x = 12$? The solution x = 3, y = 4, z = 5 would be the unordered sample (3, 4, 5). Thus there are 364 different solutions. What is the total number of positive integer solutions to the equation $x + y + x = 12$? There are 55 such solution. Each such solution would be an unordered sample where each letter is selected at least once. ___________________________________________________________________________ Multinomial Theorem We now generalize the discussion on multinomial sampling. Multinomial Sampling Suppose that a multinomial experiment consisting of $n$ independent trials with each trial resulting in exactly $k$ outcomes is performed. For convenience, these $k$ outcomes are labeled by the symbols $x_1,x_2,\cdots,x_k$. The result of the experiment can be recorded by an ordered sample, which is a string of $n$ symbols with each symbol being one of $x_1,x_2,\cdots,x_k$. The result of the experiment can also be recorded by an unordered sample, which is a sequence of $k$ numbers with the first number being the number occurrences of the outcome $x_1$, the second number being the number of occurrences of the outcome $x_2$ and so on. The number of possible ordered samples in the multinomial experiment is $k^n$. The number of ordered samples resulting in a given unordered sample $(n_1,n_2,\cdots,n_k)$ is the multinomial coefficient $\displaystyle \binom{n}{n_1,n_2,\cdots,n_k}=\frac{n!}{n_1! \ n_2! \cdots n_k!}$. The number of unordered samples in the experiment is $\displaystyle \binom{n+k-1}{n}$ based on a combinatorial argument using stars and bars. The number of unordered samples such that in each sample, each of the outcomes $x_1,x_2,\cdots,x_k$ occurs at least once is $\displaystyle \binom{n-k+k-1}{n-k}=\binom{n-k+k-1}{k-1}=\binom{n-1}{k-1}$. Number of Integer Solutions to Equations The number of non-negative integer solutions to the equation $x_1+x_2+\cdots+x_k=n$ is $\displaystyle \binom{n+k-1}{n}$, which is the total number of unordered samples as indicated above. The number of positive integer solutions to the equation $x_1+x_2+\cdots+x+k=n$ is $\displaystyle \binom{n-1}{k-1}$, which is the number of unordered samples such that each symbol from $x_1,x_2,\cdots,x_k$ occurs at least once in the multinomial sampling. There is a lot to unpack in the above two paragraphs. It is helpful to follow the random sampling idea on a specific example, either the lunch problem discussed above or another example. The ideas in the above paragraphs contains all the information for stating the multinomial theorem. Sum of all Multinomial Coefficients In the multinomial experiment described above, the sum of all possible multinomial coefficients is $k^n$, i.e. $\displaystyle \sum \limits_{a_1+a_2+\cdots a_k=n} \frac{n!}{a_1! \ a_2! \cdots a_k!}=k^n$ Multinomial Theorem The formula shown below shows how to raise a multinomial to a power. $\displaystyle (x_1+x_2+\cdots x_k)^n =\sum \limits_{a_1+a_2+\cdots a_k=n} \frac{n!}{a_1! \ a_2! \cdots a_k!} \ x_1^{a_1} x_2^{a_2} \cdots x_k^{a_k}$ The count $k^n$ is identical to the sum of all the possible multinomial coefficients in the experiment. This fact follows from the observations we make about the multinomial sampling. The count $k^n$ is the total number of all ordered samples. The ordered samples can be divided into groups where each group consists of of all ordered samples associating with the same unordered sample. Note that the size of each of these groups is a multinomial coefficient. The multinomial theorem is a compact way of describing the multinomial experiment. When it is expanded out, the left-hand-side lists out all the $k^n$ ordered samples. A typical ordered sample consists of $a_1$ many $x_1$, $a_2$ many $x_2$ and so on, which can be represented by $x_1^{a_1} x_2^{a_2} \cdots x_k^{a_k}$, which is a term on the right-hand-side. Thus a term such as $x_1^{a_1} x_2^{a_2} \cdots x_k^{a_k}$ is another way to notate an unordered sample and it represents $\frac{n!}{a_1! \ a_2! \cdots a_k!}$ many ordered samples. Thus $\frac{n!}{a_1! \ a_2! \cdots a_k!} x_1^{a_1} x_2^{a_2} \cdots x_k^{a_k}$ is the result of aggregating all the ordered samples for a given unordered sample. Summing all these aggregated results give all the possible ordered samples in the multinomial experiment. ___________________________________________________________________________ Examples The best way to absorb the concepts discussed here is to work excises. Three more examples are presented. Several exercises are given in the section below. Example 2 Suppose that 11 new hires are assigned to four office locations – the headquarter, branch office North, branch office South and branch office East. • How many assignments can be made? • How many assignments can be made such that 3 new hires are assigned to the headquarter, 3 new hires are assigned to branch office North, 4 new hires are assigned to branch office South and 1 new hire is assigned to branch office East? • How many assignments can be made such that 3 new hires are assigned to one location, 3 new hires are assigned to another location, 4 new hires are assigned to another location and 1 new hire is assigned to the remaining location? The answer to the first question is $4^{11}$ = 4,194,304. The answer to the second question is a multinomial coefficient. $\displaystyle \frac{11!}{3! \ 3! \ 4! \ 1!}=46200$ Each assignment can be viewed as a string of 11 letters, each of which is chosen from H, N, S and E (these are the ordered samples discussed above). An unordered sample is a sequence of 4 numbers. For example, the unordered sample for the second question is (3, 3, 4, 1). The third question would include other unordered samples with the numbers summing to 11, e.g. (1, 3, 4, 3). Basically we are trying to divide the 4 letters into 3 groups, one group of one letter appearing once, one group with two letters appearing 3 times each, one group with one letter appearing 4 times. This is another multinomial coefficient. $\displaystyle \frac{4!}{1! \ 1! \ 2!}=12$ Thus the answer to the third question is 12 x 46,200 = 554,400. $\square$ Example 3 Suppose that 16 new hires are assigned to four office locations – the headquarter, branch office North, branch office South and branch office East. Six of the new hires are engineers and only work in the headquarter or branch office East. The other ten new hires are technicians and can be assigned to any one of the four locations. • How many assignments can be made? • How many assignments can be made such that four of the engineers will work in the headquarter and two of the new technicians will work in the headquarter, 3 new technicians are assigned to branch office North, 4 new technicians are assigned to branch office South and 1 new technician is assigned to branch office East? • How many assignments can be made such that four of the engineers will work in either the headquarter or branch office East and two of the new technicians will work in one of the 4 locations, 3 new technicians are assigned to another location, 4 new technicians are assigned to a third location and 1 new technician is assigned to the remaining location? There are two assignments, one for engineers and one for technicians. The answer would be obtained by multiplying the two assignment counts. The answer to the first question is $2^6 \cdot 4^{11}$ = 640,000. The following is the answer to the second question. $\displaystyle \binom{6}{4} \times \frac{10!}{2! \ 3! \ 4! \ 1!}=15 \times 12600=189000$ Note that there are $\binom{6}{4}$ = 15 ways to 4 of the engineers to the headquarter (and thus assigning the other two engineers to the other office). The number of ways to assign 10 technicians to the 4 locations in the indicated numbers is the multinomial coefficient indicated above (the one resulting in 12,600). The following is the answer to the third question. $\displaystyle \binom{6}{4} \times 2 \times \frac{10!}{2! \ 3! \ 4! \ 1!} \times \frac{4!}{1! \ 1! \ 1! \ 1!}=30 \times 302400=9072000$ Note that for the third question, a second multinomial coefficient on the locations is required for each type of workers. $\square$ Example 4 Fifteen identical brand new mail delivery trucks are assigned to 5 post offices. • How many assignments can be made? • How many assignments can be made such that each post office is assigned at least one truck? The problem can be done using the combinatorial argument with stars and bars discussed above. The 15 trucks are stars and there 4 bars creating 5 spaces representing the post offices. Any assignment of trucks would be like a string of 15 stars and 4 bars. The following is an example. * * * * | * * * * * * | | * * * * * The above star-and-bar diagram shows that 4 trucks are assigned to the first post office, 6 trucks are assigned to the second post office, zero trucks are assigned to the third post office and 5 trucks are assigned to the fourth post office. What is more important to notice is that there are 19 positions in the diagram. The problem is to choose 15 of them to place the stars. The following is the answer to the first question. $\displaystyle \binom{19}{15}=3876$ The second question requires that each space has at least one star. We place one star in each space. There are 11 stars left. We now consider 11 stars and 3 bars. The following is the number of ways of arranging 11 stars in 14 positions. $\displaystyle \binom{14}{11}=364$ Thus there are 364 ways to assign 15 trucks to four post offices such that each office gets at least one truck. $\square$ ___________________________________________________________________________ Exercises Exercise 1 A father is to distribute 9 gifts to his three children. 1. In how many ways can the gifts be distributed if the eldest child is to receive 2 gifts, the middle child is to receive 2 gifts and the youngest child is to receive 5 gifts? 2. In how many ways can the gifts be distributed if one child is to receive 2 gifts, another child is to receive 2 gifts and the remaining child is to receive 5 gifts? Exercise 2 Eleven job assignments are randomly distributed to four workers Marcus, Issac, Samantha and Paul. In how many ways can these jobs be assigned to the four workers such that Marcus will receive one job, Issac will receive 4 jobs, Samantha will receive 4 jobs and Paul will receive 2 jobs? Exercise 3 1. Ten students are to be assigned to two math classes. How many ways can the students be divided into the two math classes with 5 students in each class? 2. Fifteen students are to be assigned to three math classes. How many ways can the students be divided into the three math classes with 5 students in each class? Exercise 4 An investor has 25 thousand dollars to invest among 5 possible investments. The amount to invest in each investment is in the unit of one thousand dollars. Suppose that the entire amount of 25 thousand dollars is to be invested. 1. How many different investment strategies are possible? 2. How many different investment strategies are possible if at least one unit is put into each investment choice? Exercise 5 Recall the Multinomial Lunch Problem. Each of the twelve people have 3 choices for lunch – McDonald, Burger King and IN-N-OUT, all fast food restaurants. The choice for each person is independent of the choices of the other diners. In how many ways can the lunch choices for this 12-person group be made in such a way that each restaurant is visited by at least 3 diners? $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ Answers Exercise 1 1. 756 2. 2,268 Exercise 2 34,650 Exercise 3 1. 252 2. 756,756 Exercise 4 1. 23,751 2. 10,626 Exercise 5 256,410 Hint: There are three cases, each of which requires the use of two multinomial coefficients, one for the diners and one for the restaurants. ___________________________________________________________________________ $\copyright$ 2017 – Dan Ma # Binomial coefficients This is the third post in a series of posts on combinatorial analysis. The post is opened with the following problem. Figure 1 Path Problem Point Q is 7 blocks east and 6 blocks north of Point P (see Figure 1). A person wants to walk from Point P to Point Q by walking 13 blocks. Assume that all the paths from any point to any point in the above diagram are available for walking. In how many ways can the person go from Point P to Point Q? One way to solve this problem is to count the number of paths in a “brute force” approach by tracing all possible paths in the diagram. The total number of paths is 1,716. So counting directly is not a practical approach. It turns out that the path problem and other similar problems will become routine once the concept of binomial coefficients is clearly understood. ___________________________________________________________________________ Review First we highlight the important concepts introduced in the previous post on permutations and combinations. The number $n!$, read $n$ factorial, is defined by the product $n!=n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1$. It is the number of ordered arrangements of $n$ objects. For convenience we define 0! = 1. An ordered arrangement of a set of objects is called a permutation. How many permutations are there of 7 objects? For example, how many ways can the following 7 people be arranged in a row for a group photo: Abby, Beth, Charlie, David, Edward, Frank, and George? An equivalent question: how many permutations are there of the letters A, B, C, D, E, F and G? The answer is 7! = 5040. The reasoning is based on the multiplication principle (see here). There are 7 people to choose for the first position, and there are 6 people to choose from for the second position after the first position is fixed, and so on. Thus there are 7 x 6 x 5 x 4 x 3 x 2 x 1 = 5040. The number of permutations of $k$ objects chosen from $n$ objects is defined by $\displaystyle P(n,k)=\frac{n!}{(n-k)!}$. Out of the 7 people mentioned above, how many ways can three people be randomly selected to receive three cash prizes of$1000, $500 and$100? An equivalent question: how many permutations are there of 3 letters chosen from the 7 letters A, B, C, D, E, F and G? The answer can also be obtained by the multiplication principle. There are 7 x 6 x 5 = 210 permutations, which is identical to $P(7,3)=\frac{7!}{(7-3)!}=\frac{7!}{4!}=7 \times 6 \times 5$.

The number of different groups of size $k$ that can be chosen from a set of $n$ distinct objects is $\displaystyle \binom{n}{k}=\frac{n!}{k! \ (n-k)!}$ where $n$ is a positive integer and $k=0,1,2,\cdots,n$. This number is called the number of possible combinations of $n$ objects chosen $k$ at a time. The values $\displaystyle \binom{n}{k}$ are often referred to as binomial coefficients because of their connection with the binomial theorem.

Out of the 7 people mentioned above, how many ways can three people be randomly selected to receive three cash prizes, each of which is 1000? An equivalent question: how many three-letter sets can be chosen from the 7 letters A, B, C, D, E, F and G? Here, the order does not matter. The answer 210 obtained previously is too large because it contains many repeats. For example, the letters A, B and C has 3! = 6 permutations. In the answer 210, each 3-letter combination occurs 6 times. So the answer is 210 / 6 = 35, which is identical to $\binom{7}{3}=35$. Other notations for the binomial coefficient $\binom{n}{k}$ are $_nC_k$, $C(n,k)$ and $C_{n,k}$. Permutation and combination can all be computed directly in terms of factorials. The calculation can also be done using calculator or software. Most calculators have functions for combination (binomial coefficient) and permutation. In Excel, the binomial coefficient is computed by the formula =COMBIN(n, k), which will give the result as $\binom{n}{k}$. The Excel formula for permutation is =PERMUT(n,k). ___________________________________________________________________________ The Path Problem Recall that the problem is to walk 7 blocks East and 6 blocks North starting at point P. Let use E to mean walking one block East and N to mean walking one block North. The following is one specific path that the person might take. Figure 2 The path in Figure 2 can be described by the string E-E-N-N-N-E-N-E-E-E-N-N-E. Of course there are many other possible paths that can be taken. Observe that each possible path correspond to a string of 7 E’s and 6 N’s. On the other hand, each possible 13-character string with 7 E’s and 6 N’s correspond to a path in the problem. So the problem is about finding the number of possible 13-character string with 7 E’s and 6 N’s. In other words, we are in interested in all the ways we can write 7 E’s and 6 N’s in the following 13 positions. $\LARGE \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box \ \ \ \Box$ Writing 7 E’s and 6 N’s in 13 boxes is the same as choosing 7 boxes out of 13 boxes to fill with 7 E’s. The number of ways to choose 7 objects out of 13 objects is simply $\binom{13}{7}=1716$. ___________________________________________________________________________ Several Interpretations of the Binomial Coefficients The path problem makes it clear that there are several ways of looking at the binomial coefficient $\displaystyle \binom{n}{k}$. Each of the following is a count that is computed by $\displaystyle \binom{n}{k}$. 1. The number of different groups of size $k$ that can be chosen from a set of $n$ objects. 2. The number of ways a set of $n$ objects can be labeled by 0 or 1. 3. The number of different $n$-character strings that can be formed by using $k$ of one symbol and $n-k$ of another symbol. 4. The number of permutations of $n$ items, of which $k$ are alike and $n-k$ are alike. 5. A random experiment consists of $n$ trials, each of which results in one of two outcomes (outcome 1 and outcome 2). The number of ways the experiment can be performed such that $k$ of the trials result in outcome 1 and $n-k$ of the trials result in outcome 2. 6. An urn contains a large number of balls, each of which is labeled 0 or 1. Randomly select a ball $n$ times from the urn with replacement. The number of ways the balls can be selected in such a way that $k$ of the balls are labeled 1 and $n-k$ of the balls are labeled 0. The same theme runs through the above 6 ideas. The first one is the standard definition of binomial coefficient. The number $\binom{n}{k}$, according to idea 1, would be the number of all possible subsets of size $k$ that can be chosen from a set of $n$ objects. We can also think of choosing a subset as a random experiment of $n$ trials where each trial has two distinct outcomes. Out of the $n$ objects, we only want $k$ of them with $k \le n$. Then for each object, there is a decision – choose it or not choose it (two distinct outcomes). So there are $n$ trials and each trial has two outcomes (idea 5). We can also think of a random sampling process too. Perform each trial that ends in two outcomes will be like a random sampling from a population consisting of 0’s and 1’s (idea 6). Going back to the $n$ objects in idea 1, deciding whether to choose each object is also like labeling that object with 0 or 1 (idea 2). Since each object generates two outcomes (choose or not choose), the $n$ decisions successively is like a string of $n$ characters, each of which is one of two distinct symbols (ideas 3 and 4). Though the interpretation may be nuanced, the calculation of the binomial coefficient is straightforward. Thinking of the binomial coefficient as the number of ways to making a series of two-outcome decisions is crucial to the understanding of binomial distribution. In the remainder of the post, we discuss other properties of the binomial coefficients. ___________________________________________________________________________ The Binomial Theorem The sum of two symbols, say $x+y$, is called a binomial. The binomial theorem is a formula for deriving the power of a binomial, i.e. for deriving $(x+y)^n$ for $n=1,2,3,\cdots$. We explain the idea behind the formula. The ideas 3 and 4 discussed above are particularly useful ways of looking at the binomial theorem. Consider the first several expansions. \displaystyle \begin{aligned} (x+y)^1&=x+y \end{aligned} \displaystyle \begin{aligned} (x+y)^2&=(x+y) (x+y)\\&=xx+xy+yx+yy \\&=x^2+2xy+y^2 \end{aligned} \displaystyle \begin{aligned} (x+y)^3&=(x+y) (x+y) (x+y)\\&=xxx+xxy+xyx+yxx+xyy+yxy+yyx+yyy \\&=x^3+3x^2y^1+3xy^2+y^3 \end{aligned} \displaystyle \begin{aligned} (x+y)^4&=(x+y) (x+y) (x+y) (x+y)\\&=xxxx+xxxy+xxyx+xyxx+yxxx\\& \ \ +xxyy+ xyxy+xyyx+yxxy+yxyx+yyxx\\&\ \ +xyyy+yxyy+yyxy+yyyx+yyyy \ \ \ \ \ \ \ \ \ \text{(16 terms)} \\&=x^4+4x^3y^1+6x^2y^2+4xy^3+y^4 \end{aligned} \displaystyle \begin{aligned} (x+y)^5&=(x+y) (x+y) (x+y) (x+y) (x+y)\\&=xxxxx+xxxxy+xxxyx+xxyxx+xyxxx+yxxxx \cdots \\& \ \ +xxxyy+xxyxy+xyxxy+yxxxy+xxyyx \\& \ \ + xyxyx+yxxyx+xyyxx+yxyxx+yyxxx \ \ + \cdots (\text{32 terms}) \\&=x^5+5x^4y^1+10x^3y^2+10x^2y^3+5xy^4+y^5 \end{aligned} The above derivations are deliberately detailed to make a point. For example, the result of $(x+y)^5$ is product of 5 identical factors of $x+y$. Multiplying out these five factors of $x+y$ results in $2^5=32$ terms. Each of these 32 items is a string of x’s and y’s. Let’s look at the strings with 3 x’s and 2 y’s. they are: $xxxyy+xxyxy+xyxxy+yxxxy+xxyyx$ $xyxyx+yxxyx+xyyxx+yxyxx+yyxxx$ To find out how many such strings are possible, we need to find out the number of 5-letter strings of which 3 letters are the same and the other 2 letters are the same. That would be $\binom{5}{3}=\binom{5}{2}=10$. In general, $(x+y)^n$ is obtained by multiplying $n$ factors of $x+y$. In the expansion, a typical term is $x^{n-j} y^j$, which can be viewed as a $n$-letter string of $n-j$ of the letters are $x$ and $j$ of the letters are $y$. We can also look at the situation as choosing $j$ of the $n$ positions to write the letter y. There are $\binom{n}{j}$ many ways of writing $j$ instances of y in $n$ positions. Thus $\binom{n}{j} x^{n-j} y^j$ would be one of the terms in the final result of the expansion. This is the reason why $\binom{n}{j}$ is referred to as binomial coefficients. The binomial theorem shows how to derive the power of a binomial. The formula is: $\displaystyle (x+y)^n=\binom{n}{0} x^n+\binom{n}{1} x^{n-1}y^1+\binom{n}{2} x^{n-2}y^2+\cdots+\binom{n}{j} x^{n-j}y^j+\cdots+\binom{n}{n-1} x^{1}y^{n-1}+\binom{n}{n} y^n$. A more compact way of stating the binomial theorem is: $\displaystyle (x+y)^n=\sum \limits_{j=1}^n \binom{n}{j} x^{n-j}y^j$. ___________________________________________________________________________ A Recursive Formula The combination $\displaystyle \binom{n}{k}$ can be evaluated using calculator or software. We may not need the following formula for the purpose of calculation. However, it does provide a great deal of insight. $\displaystyle \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$ The formula can be derived by the following thought process. A $k$-subset of a set of $n$ objects is a subset consisting of exactly $k$ elements. The quantity $\displaystyle \binom{n}{k}$ is the number of $k$-subsets of a set of $n$ objects. For our purpose here, the $n$ objects are the numbers $1,2,3,\cdots,n$. Let fix one of the objects, say 1. There are two types of $k$-subsets – the ones containing 1 and the ones not containing 1. The number of $k$-subsets of the first type is $\displaystyle \binom{n-1}{k-1}$. The point 1 is known to be in each $k$-subset of the first type and the other $k-1$ points must be chosen from $n-1$ objects. The number of $k$-subsets of the second type is $\displaystyle \binom{n-1}{k}$. The point 1 is not in each $k$-subset of the second type. So all $k$ are chosen from the other $n-1$ objects. Thus $\displaystyle \binom{n}{k}$ is the sum of these two numbers. ___________________________________________________________________________ Pascal’s Triangle No discussion of the binomial coefficients is complete without mentioning the Pascal’s triangle. The triangle is usually represented as an isosceles triangle (or an equilateral triangle). We use a right angle representation. $\begin{array}{rrrrrrrrr} 1 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \\ 1 & 1 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \\ 1 & 2 & 1 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \\ 1 & 3 & 3 & 1 & \text{ } & \text{ } & \text{ } & \text{ } & \text{ } \\ 1 & 4 & 6 & 4 & 1 & \text{ } & \text{ } & \text{ } & \text{ } \\ 1 & 5 & 10 & 10 & 5 & 1 & \text{ } & \text{ } & \text{ } \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 & \text{ } & \text{ } \\ 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 & \text{ } \\ 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 \end{array}$ Each row in the triangle gives the binomial coefficients in the expansion $(x+y)^n$, starting at $n=0$. Thus the second row gives the coefficients for the expansion of $(x+y)^1$, the third row gives the coefficients for $(x+y)^2$ and so on. The most interesting part about the triangle is that it is recursive. Each row is derived from the previous row. Each cell in a row is the sum of the two cells in the row above it – the cell directly above and the cell to the left of that. For example, the last row in the above triangle shows the coefficients for $(x+y)^8$. The third number from the left is 28, which is the sum of 21 and 7. The fourth element 56 is the sum of 35 (the cell directly above it) and 21 (the cell to the left of 35). As a result, any row can be derived from the previous row. The next row will be for $(x+y)^9$ have the following coefficients: 1, 9, 36, 84, 126, 126, 84, 36, 9, 1 The Pascal’s triangle is really the recursive formula discussed above. A typical cell in the triangle is the binomial coefficient $\binom{n}{k}$. The cell directly above it is $\binom{n-1}{k}$. The cell to the left of that one is $\binom{n-1}{k-1}$. ___________________________________________________________________________ How Many Subsets Are There of a Given Set? Given $n$ objects, we now know that there are $\binom{n}{k}$ many sets of $k$ elements from these $n$ objects. There are $\binom{7}{3}=35$ many sets of 3 letters from the letters C, K, M, L, T, P and O. There are several ways to come up with the answer. One way is to use the binomial theorem. Let $x=y=1$ and $n=7$. Write out the binomial theorem. The following is the result. $\displaystyle 128=2^7=(1+1)^7=\binom{7}{0}+\binom{7}{1}+\binom{7}{2}+\binom{7}{3}+\binom{7}{4}+\binom{7}{5}+\binom{7}{6}+\binom{7}{7}$ There are 128 different subsets of the 7 letters (or any other set of 7 objects). The reason is given in the right side of the above equation, which is the sum of the number of subsets with zero elements, plus the number of subsets with exactly one element, plus the number of subsets with exactly two elements, …, plus the number of subsets with seven elements. When buying a hamburger at a fast food restaurant, customers can always add toppings. A basic hamburger comes with a beef patty inside a bun. A customer can choose to add toppings from this list: Cheese, Ketchup, Mustard, Lettuce, Tomato, Pickles and Onion (compare the first letters with the 7 letters indicated earlier). How many different hamburgers can be created? Basically the problem is to find out the number of different subsets of the 7 letters C, K, M, L, T, P and O. The answer is of course $2^7=128$. Interestingly the answer of 128 includes one choice that is the plain burger with no toppings – just the beef and the bun. So the total number of different hamburgers with at least one topping would be 127. In general, the total number of subsets of a set with $n$ elements is $2^n$. This is confirmed by the plugging $x=1$ and $y=1$ into the binomial theorem: $\displaystyle 2^n=(1+1)^n=\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\binom{n}{3}+\cdots+\binom{n}{n-1}+\binom{n}{n}$ ___________________________________________________________________________ Exercises Exercise 1 Starting at Point P, a student walks 6 blocks to a diner for breakfast (represented by the red dot in the following diagram). After breakfast, the students 7 blocks to school that is located at Point Q. In how many ways can the student walk from Point P to Point Q? Assume that all the paths from any point to any point in the above diagram are available for walking. Figure 2 Exercise 2 In ordering a pizza, a customer can choose from a list of 10 toppings: mushroom, onion, olive, bell pepper, pineapple, spinach, extra cheese, sausage, ham, and pepperoni. • How many different pizza can the customer create if any topping in the list is desirable to the customer and if the customer chooses at least one topping? • Suppose that the customer is a meat lover. He will always choose the three meat toppings: sausage, ham and pepperoni. He will also choose up to 3 vegetable toppings. How many different pizza can the customer create? Exercise 3 A committee of 8 people is to be chosen from a class consisting of 8 men and 9 women. If the committee must consist of at least 3 men and at least 4 women, how many different committees are possible? Exercise 4 • In how many ways can a father divide 8 gifts among his two children if the eldest is to receive 5 gifts and the other child 3 gifts? • In how many ways can a father divide 8 gifts among his two children if one child is to receive 5 gifts and the other child 3 gifts? $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ Answers Exercise 1 315 Exercise 2 • 1023 • 792 Exercise 3 15876 Exercise 4 • 56 • 112 ___________________________________________________________________________ $\copyright \ 2017 \text{ by Dan Ma}$ # Permutations and combinations This is the second post in a series of posts on combinatorial analysis. The first post is on the multiplication principle. This post introduces permutations and combinations. The starting point of the discussion on counting is the idea that if one event can occur in $M$ ways and another event can occur, independent of the first event, in $N$ ways, then the two events together can occur in $M \times N$ ways. This idea is often called the multiplication principle and is introduced in this previous post. ___________________________________________________________________________ Factorial Consider the eight letters A, B, C, D, E, F, G and H. How many ways can we order the 8 letters? The following shows two ordered arrangements. A-B-C-D-E-F-G-H C-B-F-A-D-G-H-E The multiplication principle can help us determine the number of all arrangements of 8 letters. We are trying to fill 8 objects into 8 positions. There are 8 choices for the first position. After the first letter is fixed, there are 7 letters for the second position. Continue with this approach, there will be only one letter left for the eighth position. In total, there are 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 40,320 ordered arrangements of 8 letters. A convenient notation for the answer is 8!, read 8 factorial. It is simply the product of the integers from 8 down to 1. In general, if $n$ is a positive integer, $n!$, read $n$ factorial, is the product of all the integers from $n$ down to 1. $n!=n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1$ For the above definition of $n!$ to make sense, $n$ is a positive integer. We define 0! = 1 to make certain formulas easy to calculate. According to the above example, there are 8! many different ordered arrangements of 8 distinct objects (objects that are distinguishable from one another). Any ordered arrangement such as C-B-F-A-D-G-H-E is called a permutation of the 8 letters. In general, a permutation is an ordered arrangement of a set of objects that are distinguishable from one another. From the above example of 8 letters, we have the following observation. The total number of permutations of $n$ distinct objects is $n!$. The G8 summit is an annual meeting between leaders from eight of the most powerful countries in the world. There would be 8! = 40,320 different ways to line up the 8 leaders for a group photo. A permutation can be viewed as ranking. In a soccer league of 8 teams, there would be 8! = 40,320 different possible rankings. The factorial grows very rapidly. In ordering 9 objects, there are 9! = 362,880 permutations. 10! = 3,628,800 11! = 39,916,800 12! = 479,001,600 15! = 1,307,674,368,000 17! = 355,687,428,096,000 20! = 2,432,902,008,176,640,000 Thus the number of possible rankings of 12 job applicants is over 479 millions. The number of possible rankings of 20 job applicants would be a staggering number, over 2.4 quintillions! A quintillion is 10 raised to 18. In contrast, a trillion is 10 raised to 12. Example 1 Suppose that you have 12 books with 4 of them being novels, 4 of them being math books, 3 of them being science books and one being a history book. You want to place the books on the same level in a bookshelf. If the books are put in any order, then there would be 12! = 479,001,600 different placements of books. In how many ways can the books be placed in the bookshelf if all books of the same subject are to be together? The last question makes use of the multiplication principle in a subtle way. Consider the books arranged by subjects in this order: novel-math-science-history. By the multiplication principle, there are 4! x 4! x 3! x 1! = 24 x 24 x 6 x 1 = 3,456 many ordered arrangements. This is just for one specific way of the order of the 4 subjects – novel-math-science-history. There are 4! = 24 ways of order 4 subjects. Then the answer to the last question is 24 x 3,456 = 82,944. $\square$ ___________________________________________________________________________ Permutation Sometimes we do not order the entire set of $n$ objects. We only order a subset of the $n$ objects. Using the above example of 8 letters A, B, C, D, E, F, G and H, in how many ways can we arrange three letters from these 8 letters? The multiplication principle is at work here. We are attempting to fill 3 positions using 8 letters at our disposal. The first position has 8 choices. The second position has 7 choices and the third position has 6 choices. There are a total of 8 x 7 x 6 = 336 ordered arrangements. Three examples are A-B-C, G-A-H and E-B-F. Any one of these 336 ordered arranged is called 3-permutation of 8 letters. We can also call it a permutation of 8 letters taken 3 at a time. Example 2 To put the 8 letters in a context, suppose that a math club has 8 students – Abby, Beth, Chloe, Diane, Edward, Frank, George and Henry. In how many ways can we choose 3 students to fill three positions of President, Vice President and Treasurer of the math club? Based on the preceding discussion, the answer is 8 x 7 x 6 = 336. The following is a presentation of the calculation that gives the hint for a formula. $\displaystyle 8 \times 7 \times 6=\frac{8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{5 \times 4 \times 3 \times 2 \times 1}=\frac{8!}{5!}=\frac{8!}{(8-3)!}$ In general, any ordered arrangement of $k$ objects from a set of $n$ objects is called a $k$-permutation of $n$ objects. We can also call any such ordered arrangement a permutation of $n$ objects taken $k$ at a time. Here, we attempt to fill $k$ positions with objects selected from $n$ objects with $k \le n$. How many permutations of $n$ objects taken $k$ at a time? There are $n \times (n-1) \times (n-2) \times \cdots \times (n-(k-1))$ many different permutations of $n$ objects taken $k$ at a time. Some common notations for this number are $P(n,k)$ or $P_{n,k}$. According to the hint in Example 2, the following is a formula for $P(n,k)$. $\displaystyle P(n,k)=\frac{n!}{(n-k)!}$ is the number of permutations of $n$ objects taken $k$ at a time. Note that $P(n,n)$ is simply $n!$. Example 3 In evaluating 20 job applicants, there are 20! many possible rankings, which is over 2 quintillions as discussed above. A more sensible goal is to narrow the list to the top 5 candidates. The number of permutations of 20 candidates taken 5 at a time is $\displaystyle P(20,5)=\frac{20!}{15!}=20 \times 19 \times 18 \times 17 \times 16=\text{1,860,480}$ Example 4 Suppose that the psychology club at a university has 12 members in the lower division (consisting of freshmen and sophomores), 10 members in the upper division (consisting of juniors and seniors). Four awards (achievements in terms of overall grade, leadership potential, volunteerism, and public speaking) are given to each group. What is the total number of different outcomes if • a student can receive more than one award, • a student can receive only one award. If a student can be awarded more than once, then there are $12^4$ ways of giving out awards in the lower division and $10^4$ ways in the upper division, leading to the following answer. $\displaystyle 12^4 \times 10^4 = \text{207,360,000}$ If a student can only be awarded once, then the following is the answer. $\displaystyle P(12,4) \times P(10,4) =(12 \times 11 \times 10 \times 9) \times (10 \times 9 \times 8 \times 7)= \text{59,875,200}$ ___________________________________________________________________________ When Some Objects are Indistinguishable In calculating the number of permutations, the objects are assumed to be distinct. We now look at the situation where objects are separated into groups of indistinguishable objects. The goal is still finding the number of ordered arrangements. The number of permutations as calculated above would be an over count. The answer is obtained by dividing the inflated count by the amount of over counting. Example 5 How many different letter arrangements can be formed from the letters in the word BANANA? There are 6 letters in BANANA. Three of the letters are indistinguishable (A) and two of them are indistinguishable (N). If all the letters are distinguishable, then there are 6! permutations. But 6! = 720 over counts. By how many? Pretend all the letters are distinguishable. Take the arrangement $A_1 \ A_2 \ A_3 \ B \ N_1 \ N_2$. Now permute the A’s and the N’s. Doing so should result in 3! x 2! = 12 permutations. $A_1 \ A_2 \ A_3 \ B \ N_1 \ N_2$ $A_1 \ A_3 \ A_2 \ B \ N_1 \ N_2$ $A_2 \ A_1 \ A_3 \ B \ N_1 \ N_2$ $A_2 \ A_3 \ A_1 \ B \ N_1 \ N_2$ $A_3 \ A_1 \ A_2 \ B \ N_1 \ N_2$ $A_3 \ A_2 \ A_1 \ B \ N_1 \ N_2$ $A_1 \ A_2 \ A_3 \ B \ N_2 \ N_1$ $A_1 \ A_3 \ A_2 \ B \ N_2 \ N_1$ $A_2 \ A_1 \ A_3 \ B \ N_2 \ N_1$ $A_2 \ A_3 \ A_1 \ B \ N_2 \ N_1$ $A_3 \ A_1 \ A_2 \ B \ N_2 \ N_1$ $A_3 \ A_2 \ A_1 \ B \ N_2 \ N_1$ But in reality, all of the 12 permutations are the same: $A \ A \ A \ B \ N \ N$. So each unique permutation appears 12 times in the count 6!. Thus the correct count is $\displaystyle \frac{6!}{3! \ 2! \ 1!}=60$ In general, $\displaystyle \frac{n!}{m_1! \ m_2! \ \cdots \ m_k!}$ is the number of permutations of $n$ objects, of which $m_1$ are alike, $m_2$ are alike, …, $m_k$ are alike, where $m_1+\cdots+m_k=n$. ___________________________________________________________________________ Combination In all the above instances of counting, the focus is to find all ordered arrangements (or permutations) of a set of objects. We now focus on the different subsets of $k$ elements that can be chosen from a set of $n$ objects. In this setting, the goal is not to count ordered arrangements. The goal is to count the number of subsets of a certain size. For example, let’s say you want to buy a 2-scoop ice cream cone of different flavors chosen from 3 flavors – Chocolate (C), Strawberry (S) and Vanilla (V). Suppose you do not care which flavor is on top and which one is at the bottom. The different subsets of size 2 would be: CS, CV, and SV. Here, CS is not an ordered arrangement. It just means that the two chosen flavors are chocolate and strawberry. If order matters, then there would be six outcomes – CS, SC, CV, VC, SV, and VS. So the approach is to find the number of permutations (an over count) and then divide the amount of over count. Example 6 Suppose that a math club has 8 students – Abby, Beth, Chloe, Diane, Edward, Frank, George and Henry. In how many ways can we choose three students to form a committee of three? The number of permutations of three students is 8 x 7 x 6 = 336. This count is inflated since there are many repeats reflected in this count. For example, if the chosen students are Abby, Beth and Chloe, then there are 3! = 6 ways to order these three students – ABC, ACB, BAC, BCA, CAB and CBA. So each set of three students is reflected 6 times in the inflated count of 336. So the answer is 336 / 6 = 56. Thus there are 56 possible groups of three students when three students are chosen from 8 students. The following calculation makes the formula clear. $\displaystyle \frac{8 \times 7 \times 6}{3!}=\frac{8 \times 7 \times 6 \times 5!}{3! \ 5!}=\frac{8!}{3! \ 5!}$ In general, $\displaystyle \binom{n}{k}=\frac{n!}{k! \ (n-k)!}$ is the number of different groups of size $k$ that could be chosen from a set of $n$ distinct objects where $k=0,1,2,\cdots,n$. The number $\binom{n}{k}$ is called a binomial coefficient and is pronounced “$n$ choose $k$.” Other notations for $\binom{n}{k}$ are $_nC_k$, $C_{n,k}$ and $C(n,k)$. Example 7 A committee of five is to be chosen from a group of 11 people consisting of 5 men and 6 women. • How many different committees of five people can be formed? • How many different committees consisting of 2 men and 3 women can be formed? • How many different committees of five consisting of either 2 men or 2 women? The number of possible committees of five would be $\binom{11}{5}=462$. For the second problem, note that there are $\binom{5}{2}=10$ possible groups of 2 men and there are $\binom{6}{3}=20$ groups of 3 women. By the multiplication principle, there are 10 x 20 = 200 different groups of 5 people consisting of 2 men and 3 women. For the third problem, there are two cases: a committee of 2 men and 3 women or a committee of 2 women and 3 men. The answer is the sum of these two cases. Thus the answer is $\displaystyle \binom{5}{2} \times \binom{6}{3}+\binom{5}{3} \times \binom{6}{2}=10 \times 20+10 \times 15=350$ ___________________________________________________________________________ More Examples We present a few more examples to demonstrate the ideas discussed here. Exercises are given at the end. Example 8 A child plays with a set of 12 blocks, 4 of which are red, 4 of which are black, 3 of which are white and one of which is yellow. In how many ways can these blocks be arranged in a row? In how many ways can these blocks be arranged in a row in such a way that all blocks of the same color are together? Note the similarity with Example 1. Both problems concern with a collection of 12 objects that can be separated into 4 sub groups. In Example 1, the objects in each sub group are distinguishable while the objects in this example are indistinguishable in each sub group. As a result, the formula discussed in the section “When Some Objects are Indistinguishable” would apply. Here’s the number of different ways to order the blocks. $\displaystyle \frac{12!}{4! \ 4! \ 3! \ 1!}=\text{138,600}$ For the second question, the answer would be 4! = 24. Unlike Example 1, we do not need to order the blocks within the same color since they are indistinguishable. $\square$ Example 9 The tennis team in School A has 12 players and the tennis team in School B has 14 players. If 5 players are selected from each team and then paired off for a tennis game, how many results are possible? There are $\binom{12}{5}=792$ ways of choosing 5 players from Team A. There are $\binom{14}{5}=2002$ ways of choosing 5 players from Team B. There are 5! = 120 ways in pairing off the two teams of 5 players. Thus there are 792 x 2002 x 120 = 190,270,080 ways of choosing two teams and then pairing them off for a tennis game. $\square$ Example 10 A company is made up of 3 departments with the one department consisting of 8 employees, the second department consisting of 10 employees and the third department consisting of 5 employees. The owner of the company decides to promote two employees chosen from the 23 employees. Suppose that the two employees are selected at random. How many ways can the two employees be selected if • both promotions are from the same department? • both promotions are from different departments? The problem does not mention the positions for the promotion. Thus we assume that the two positions are identical. The first question has three cases based on the departments. The following is the sum of the three cases. $\displaystyle \binom{8}{2}+\binom{10}{2}+\binom{5}{2}=28+45+10=83$ For the second question, there are $\binom{3}{2}=3$ cases, based on pairs of departments. The following is the sum of the 3 cases. $\displaystyle \binom{8}{1} \times \binom{10}{1}+\binom{8}{1} \times \binom{5}{1}+\binom{10}{1} \times \binom{5}{1}=80+40+50=170$ Example 11 The problem is the same as Example 10 except that the two promotions are for President and Vice President. Now that the two promotions are different, order matters. Thus use permutations to perform the calculations. the answer to the first question is: $\displaystyle \frac{8!}{(8-2)!}+\frac{10!}{(1-2)!}+\frac{5!}{(5-2)!}=56+90+20=166$ In the second question, we still pick one person from each department, but it needs to be multiplied by two since the positions are different. $\displaystyle 2 \times 8 \times 10+2 \times 8 \times 5+2 \times 10 \times 5=160+80+100=340$ ___________________________________________________________________________ Exercises Exercise 1 How many different letter arrangements can be formed from the letters in the word MISSISSIPPI? Exercise 2 In how many ways can a manager assigns 3 different jobs at random to 11 available workers? Exercise 3 Suppose that the license plates for a certain state consist of three numbers and three letters. How many different license plates are possible if 1. the letters must come before the numbers? 2. all letters must appear together and all numbers must appear together? 3. only the letters must appear together? 4. there is no restriction on the positions of the letters and numbers? Exercise 4 In ordering a pizza, cheese and tomato sauce come with the pizza. The customer can also choose to add toppings from the following lists: Meat items: ham, sausage, pepperoni, salami, chicken. Vegetable items: pineapple, olive, mushroom, onion, bell peppers. 1. How many distinct pizzas are possible? 2. Suppose that a customer does not like salami and sausage in the meat list and onion and olive in the vegetable list and thus will not add these toppings. How many different pizzas are possible? 3. Suppose that a customer would like to add two meat items and three vegetable items as toppings. How many different pizzas are possible? 4. Suppose that a customer would like to add exactly 5 toppings. How many different pizzas are possible? 5. Suppose that a customer would like to add at most 5 toppings. How many different pizzas are possible? Exercise 5 1. Twelve workers are randomly assigned to work in four factories with 3 workers assigned to each factory as assembly line workers. How many ways can the workers be assigned to the factories? 2. Twelve workers are randomly assigned to work in four factories with 3 workers assigned to each factory as manager, assistant manager and assembly line worker. How many ways can the workers be assigned to the factories? $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ $\text{ }$ Answers Exercise 1 34,650 Exercise 2 990 Exercise 3 1. 17,576,000 2. 35,152,000 3. 70,304,000 4. 351,520,000 Exercise 4 1. 1024 2. 64 3. 100 4. 252 5. 638 Exercise 5 1. 369,600 2. 479,001,600 ___________________________________________________________________________ $\copyright \ 2017 \text{ by Dan Ma}$ # The multiplication principle This is the first post in a series of posts on combinatorial analysis, which is a study on counting, e.g. finding effective methods for counting the number of ways to arrange objects and for counting the number of ways events can occur. Many problems in mathematics, e.g. in probability theory, require the counting of the number of ways an event can occur. Permutations and combinations are basic ideas in counting. Both ideas are based on an idea called the multiplication principle. This post focuses on the multiplication principle. The next post is on permutations and combinations. ___________________________________________________________________________ The Multiplication Principle Let’s start with some examples. Example 1 Jack is buying ice cream – two scoops of ice cream of the same flavor on either a cone or a cup. The available flavors are vanilla, strawberry, chocolate, butter pecan, mint chocolate chips and rocky road. How many possible arrangements of ice cream are available for Jack? The answer is 2 x 6 = 12 arrangements. The following lists out all the possibilities. Cone-Vanilla Cone-Strawberry Cone-Chocolate Cone-Butter Pecan Cone-Mint Chocolate Chips Cone-Rocky Road Cup-Vanilla Cup-Strawberry Cup-Chocolate Cup-Butter Pecan Cup-Mint Chocolate Chips Cup-Rocky Road With the cone option, there are 6 choices for flavors. With the cup option, there are also 6 choices for flavors. So the total number of possible choices would be 6 + 6 = 2 x 6 = 12. Of course, if Jack only limits his purchase to his most favorite ice cream (say mint chocolate chips), then there would be only two choices, cone or cup. But if he is indifferent to the flavors, there would be 12 arrangements as listed above. $\square$ The listing in Example 1 suggests a general principle. The Multiplication Principle If one event can occur in $M$ ways and another event can occur independent of the first event in $N$ ways, then the two events successively can occur in $M \times N$ ways. Of course, the principle just described has an obvious generalization. Instead of just considering two events, we can count how many ways a series of events can occur. As long as the events are independent, the total number of ways all events occurring in a row is obtained by simply multiplying the numbers of possible occurrences of the individual events. Example 2 The following is a menu for a banquet. Assuming that each guest can only pick one item for each course, how many different possible dinner decisions are possible? This problem is mentioned in previous post. Using the multiplication principle, the answer is 4 x 2 x 3 x 2 = 48 choices. $\square$ Remark. For the multiplication principle to apply, the events must be independent. This means that the number of occurrences of the one event is not restricted by the previous event. If a guest in the banquet is indifferent to all items in the menu (if taken individually) but does not like to mix certain items (e.g. he does not like to have French onion soup to go with goat cheese salad), then he or she might not have 48 choices. The following example illustrates that for a certain kind of dependency between events, the multiplication principle can still apply. Example 3 A PIN code for a bank ATM machine is a 4-digit number. Determine the following: • How many PIN codes are possible? • How many PIN codes are possible if no repetition of digits is allowed? • How many PIN codes are possible if the first two digits form a number less than or equal to 33 and the last two digits form a number that is at least 3 times the first two digits? There are $10 \times 10 \times 10 \times 10= 10^4=10,000$ many possible codes. If no digits can repeat, then there are $10 \times 9 \times 8 \times 7=5040$ different codes. For the no repetition case, there are 10 choices for the first digit. Once the first digit is fixed, there are only 9 choices for the second digit. Once the first two digits are fixed, there are 8 choices for the third digit. Then the fourth digit has 7 choices once the first three digits are fixed. Though the number of choices for each digit is limited by the previous digit, it is the same regardless the value of the previous digits. Thus the principle still applies. The third problem illustrates a dependency that makes the multiplication principle not applicable. For example, if the first two digits are 01, the last two digits would be 03, 04, 05, 06, …, 99 for a total of 97 possibilities. If the first two digits are 02, then there are 94 possibilities for the last two digits (06, 07, …, 99). As the number for the first two digits increases to 33, the number of choices for the last two digits would decrease. The largest possibility for the first two digits would be 33 and there is only one choice for the last two digits (99). Thus the multiplication principle would not work here. The answer is not obtained by multiplication. It is obtained by adding up all the possibilities as the first two digits go from 01 to 33. We perform the calculation in Excel and the answer is 1617. Of course, the third problem is not a realistic way to obtain pass codes. It is just an illustration of a case where the multiplication principle does not apply. $\square$ We look at more examples. Example 4 In how many ways can 9 students (4 males and 5 females) stand in a row for a group photo • if there is no restriction on the standing positions? • if the females must stand together and the males must stand together? • if the females must stand together? If the students can stand anywhere they want, there are 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 362,880 ways of arranging these 9 students in a row. For the first spot, there are 9 students to choose from and there are 8 students to choose from for the second spot and so on. A convenient notation for the answer is 9! (read 9 factorial). It simply means that it is the product of all the integers from 9 down to 1. By the same reasoning, there are 5! = 120 ways of arranging 5 persons in a row. There are 4! = 24 ways of arranging 4 people standing in a row. If the females stand on the left and the males stand on the right, then there are 120 x 24 = 2,880 arrangements in a row for the 9 students. The answer is 2 x 120 x 24 = 5,760 since there is also the case of males standing on the left and females on the right. The third problem requires that only the females must stand together. The use of the multiplication principle is subtle. If the females must stand together, think of all the females as one unit. There are 5 units – 4 males and one combined unit of females. There are 5! ways of arranging the 5 units. Within the combined unit of females, there are 5! ways of arranging the 5 females. Thus the answer is 5! x 5! = 120 x 120 = 14,400. $\square$ The next example shows that the multiplication principle is invaluable in calculating large numbers. Example 5 In general, longer passwords are stronger passwords. The principle of counting discussed here can be used to quantify the strength. Consider an 8-character password consisting of letters from English. To start, let’s say the letters in the password are all upper case or all lower case, i.e. the password is case insensitive. Then the number of possible passwords would be $\displaystyle 26 \times 26 \times 26 \times 26 \times 26 \times 26 \times 26 \times 26=26^8=\text{208,827,064,576}$ That’s over 208.8 billions possibilities. What if the password is case sensitive? If each character in the password can be in upper case or in lower case, then each character has 52 choices (26 upper case letters and 26 lower case letters). Then the number of possible passwords would be $\displaystyle 52 \times 52 \times 52 \times 52 \times 52 \times 52 \times 52 \times 52=52^8=\text{53,459,728,531,456}$ That’s over 53 trillions possible passwords! Of course, the length of the password by itself may not mean strength. For example, people may use familiar words to form the password. One of the famous examples would have to be “Password”. In addition to being long enough, the characters in the passwords should be randomly chosen if possible. To make the 8-character password even stronger, we can include numbers in addition to letters. Then the total number of possibilities is $\displaystyle 62^8=\text{218,340,105,584,896}$ which is over 218 trillions. $\square$ ___________________________________________________________________________ Factorial The factorial concept introduced in Example 4 is a useful tool in counting. If $n$ is a positive integer, the number $n!$ is defined to be the product of all the positive integers less than or equal to $n$. $n!=n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1$ For convenience, we define 0! = 1. In Example 4, 9! is the number of ways of ordering 9 people in a row. In general, $n!$ is the number of ordered arrangements of $n$ distinct objects. There will be more discussion about this interpretation of $n$ factorial in the next post. ___________________________________________________________________________ Exercises Exercise 1 Example 3 and Example 5 concern with finding the number of possible ordered arrangements of objects for use in setting passwords or pass codes. Here’s is an example involving license plates. When a motor vehicle authority (or some relevant governmental body) designs license plates for automobiles, one important goal is to have a sufficiently large number of possibilities to accommodate all the vehicles in that jurisdiction. Suppose that the license plate has 7 characters. The first character is a number and the next three characters are letters. The last three characters are numbers. 1. What is the total number of possibilities in this license plate design? 2. If the motor vehicle authority is beginning to issue license plates with the first digit being 3, how many license plates will the authority have to issue before switching to using 4 as the first digit? Exercise 2 1. Twelve tasks are to be assigned to twelve workers. What is the total different number of job assignments? 2. In how many ways can four students be randomly selected to receive four cash prizes (10, $20,$30, \$40)?

Exercise 3

1. In how many ways can 4 boys and 4 girls stand together in a row for a group photo?
2. In how many ways can 4 boys and 4 girls stand together in a row for a group photo if people of the same gender must be together?
3. In how many ways can 4 boys and 4 girls stand together in a row for a group photo if only the girls must be together?
4. In how many ways can 4 boys and 4 girls stand together in a row for a group photo if no people of the same gender can stand together?

$\text{ }$

$\text{ }$

$\text{ }$

$\text{ }$

$\text{ }$

$\text{ }$

Exercise 1

• 175,760,000
• 17,576,000

Exercise 2

• 479,001,600
• 11,880

Exercise 3

• 40,320
• 1,152
• 2,880
• 1,152

___________________________________________________________________________
$\copyright \ 2017 \text{ by Dan Ma}$