Combinatorial probability temple university

Pdf File 257.10 KByte, 46 Pages

Chapter 2

Combinatorial Probability

2.1 Permutations and combinations

As usual we begin with a question: Example 2.1. The New York State Lottery picks 6 numbers out of 59, or more precisely, a machine picks 6 numbered ping pong balls out of a set of 59. How many outcomes are there? The set of numbers chosen is all that is important. The order in which they were chosen is irrelevant.

To work up to the solution we begin with something that is obvious but is a key step in some of the reasoning to follow. Example 2.2. A man has 4 pair of pants, 6 shirts, 8 pairs of socks, and 3 pairs of shoes. Ignoring the fact that some of the combinations may look ridiculous, in how many ways can he get dressed? We begin by noting that there are 4 ? 6 = 24 possible combinations of pants and shirts. Each of these can be paired with one of 8 choices of socks, so there are 192 = 24 ? 8 ways of putting on pants, shirt, and socks. Repeating the last argument one more time, we see that for each of these 192 combinations there are 3 choices of shoes, so the answer is

4 ? 6 ? 8 ? 3 = 576ways

The reasoning in the last solution can clearly be extended to more than four experiments, and does not depend on the number of choices at each stage, so we have The multiplication rule. Suppose that m experiments are performed in order and that, no matter what the outcomes of experiments 1, . . . , k - 1 are, experiment k has nk possible outcomes. Then the total number of outcomes is n1 ? n2 ? ? ? nm. Example 2.3. How many ways can 5 people stand in line?

31

32

CHAPTER 2. COMBINATORIAL PROBABILITY

To answer this question, we think about building the line up one person at a time starting from the front. There are 5 people we can choose to put at the front of the line. Having made the first choice, we have 4 possible choices for the second position. (The set of people we have to choose from depends upon who was chosen first, but there are always 4 people to choose from.) Continuing, there are 3 choices for the third position, 2 for the fourth, and finally 1 for the last. Invoking the multiplication rule, we see that the answer must be

5 ? 4 ? 3 ? 2 ? 1 = 120

Generalizing from the last example we define n factorial to be

n! = n ? (n - 1) ? (n - 2) ? ? ? 2 ? 1

(2.1)

To see that this gives the number of ways n people can stand in line, notice that there are n choices for the first person, n - 1 for the second, and each subsequent choice reduces the number of people by 1 until finally there is only 1 person who can be the last in line.

Note that n! grows very quickly since n! = n ? (n - 1)!.

1! 1 2! 2 3! 6 4! 24 5! 120 6! 720

7!

5,040

8!

40,320

9!

362,880

10! 3,628,800

11! 39,916,800

12! 479,001,600

The number of ways we can put the 22 volumes of an encyclopedia on a shelf is

22! = 1.24000728 ? 1021

Here we have used our TI-83. We typed in 22 then used the MATH button to get to the PRB menu and scroll down to the fourth entry to get the ! which gives us 22! after we press ENTER.

The number of ways that cards in a deck of 52 can be arranged is

52! = 8.065817517 ? 1067

Before there were calculators, people used Stirling's formula

n! (n/e)n 2n

When n = 52, 52/e = 19.12973094 and 2n = 18.07554591 so

52! (19.12973094)52 ? 18.07554591 = 8.0529 ? 1067

(2.2)

Example 2.4. Twelve people belong to a club. How many ways can they pick a president, vice-president, secretary, and treasurer?

2.1. PERMUTATIONS AND COMBINATIONS

33

Again we think of filling the offices one at a time in the order in which they were given in the last sentence. There are 12 people we can pick for president. Having made the first choice, there are always 11 possibilities for vice-president, 10 for secretary, and 9 for treasurer. So by the multiplication rule, the answer is

12 11 10 9 = 11, 800

P V ST

To compute P12,4 with the TI-83 calculator: type 12, push the MATH button, move the cursor across to the PRB submenu, scroll down to nPr on the second row, and press ENTER. nPr appears on the screen after the 12. Now type 4 and press ENTER.

Passing to the general situation, if we have k offices and n club members then the answer is

n ? (n - 1) ? (n - 2) ? ? ? (n - k + 1)

To see this, note that there are n choices for the first office, n - 1 for the second, and so on until there are n - k + 1 choices for the last, since after the last person is chosen there will be n - k left. Products like the last one come up so often that they have a name: the number of permutations of k objects from a set of size n, or Pn,k for short. Multiplying and dividing by (n - k)! we have

(n - k)!

n!

n ? (n - 1) ? (n - 2) ? ? ? (n - k + 1) ?

=

(n - k)! (n - k)!

which gives us a short formula, n!

Pn,k = (n - k)!

(2.3)

The last formula would give us the answer to the lottery problem if the order in which the numbers drawn was important. Our last step is to consider a related but slightly simpler problem.

Example 2.5. A club has 23 members. How many ways can they pick 4 people to be on a committee to plan a party?

To reduce this question to the previous situation, we imagine making the committee members stand in line, which by (2.3) can be done in 23 ? 22 ? 21 ? 20 ways. To get from this to the number of committees, we note that each committee can stand in line 4! ways, so the number of committees is the number of lineups divided by 4! or

23 ? 22 ? 21 ? 20 = 23 ? 11 ? 7 ? 5 = 8, 855

1?2?3?4

To compute C23,4 with the TI-83 calculator: type 23, push the MATH button, move the cursor across to the PRB submenu, scroll down to nCr on the third

34

CHAPTER 2. COMBINATORIAL PROBABILITY

row, and press ENTER. nCr appears on the screen after the 23, now type 4 and press ENTER.

Passing to the general situation, suppose we want to pick k people out of a group of n. Our first step is to make the k people stand in line, which can be done in Pn,k ways, and then to realize that each set of k people can stand in line k! ways, so the number of ways to choose k people out of n is

Cn,k

=

Pn,k k!

=

n! k!(n - k)!

=

n ? (n - 1) ? ? ? (n - k 1?2???k

+ 1)

(2.4)

by (2.4) and (2.1). Here, Cn,k is short for the number of combinations of k

things taken from a set of n. Cn,k is often written as

n k

,

a

symbol

that

is

read as "n choose k." We are now ready for the

Answer to the Lottery Problem, Example 2.1. We are choosing k = 6 objects out of a total of n = 59 when order is not important, so the number of possibilities is

59!

59 ? 58 ? 57 ? 56 ? 55 ? 54

C59,6 = 6!53! =

1?2?3?4?5?6

= 59 ? 58 ? 19 ? 7 ? 11 ? 9 = 45, 057, 474

You should consider this the next time you think about spending $1 for two chances to win a jackpot that starts at $3 million and increases by $1 million each week there is no winner.

Example 2.6. World Series (continued). Using (2.4) we can easily compute the probability that the series last seven games. For this to occur the score must be tied 3-3 after six games. The total number of outcomes for the first 6 games is 26 = 64. The number that end in a 3-3 tie is

6! 6 ? 5 ? 4 C6,3 = 3! 3! = 1 ? 2 ? 3 = 20

since the outcome is determined by choosing the three games that team A will win. This gives us a probability of 20/64 = 5/16 for the series to end in seven games. Returning to the calculation in the previous section, we see that the number of outcomes that lead to A winning in six games is the number of ways of picking two of the first five games for B to win or C5,2 = 5!/(2! 3!) = 5?4/2 = 10.

Example 2.7. Suppose we flip five coins. Compute the probability that we get 0, 1, or 2 heads.

There are 25 = 32 total outcomes. There is only 1, T T T T T that gives 0 heads. If we want this to fit into our previous formula we set 0! = 1 (there is only one way for zero people to stand in line) so that

5! C5,0 = 5! 0! = 1

2.1. PERMUTATIONS AND COMBINATIONS

35

There are 5 outcomes that have one heads. We can see this by writing out the possibilities: HT T T T , T HT T T , T T HT T , T T T HT , and T T T T H, or note that the number of ways to pick 1 toss for the heads to occur is

5! C5,1 = 4! 1! = 5

Extending the last reasoning to two heads, the number of outcomes is the number of ways of picking 2 tosses for the heads to occur or

5! 5 ? 4 C5,2 = 3! 2! = 2 = 10

By symmetry the numbers of outcomes for 3, 4, and 5 heads are 10, 5, and 1. In terms of binomial coefficients this says

Cn,m = Cn,n-m

(2.5)

The last equality is easy to prove: The number of ways of picking m objects out of n to take is the same as the number of ways of choosing n - m to leave behind. Of course, one can also check this directly from the formula in (2.4).

Pascal's triangle. The number of outcomes for coin tossing problems fit together in a nice pattern:

1

1

1

1

2

1

1

3

3

1

1

4

6

4

1

1

5

10

10

5

1

1

6

15

20

15

6

1

1

7

21

35

35

21

7

1

Each number is the sum of the ones on the row above on its immediate left and

right. To get the 1's on the edges to work correctly we consider the blanks to

be zeros. In symbols

Cn,k = Cn-1,k-1 + Cn-1,k

(2.6)

Verbal proof. In picking k things out of n, which can be done in Cn,k ways, we may or may not pick the last object. If we pick the last object then we must complete our set of k by picking k - 1 objects from the first n - 1, which can be done in Cn-1,k-1 ways. If we do not pick the last object then we must pick all k objects from the first n - 1, which can be done in Cn-1,k ways.

Analytic proof. Using the definition (2.4)

(n - 1)!

(n - 1)!

Cn-1,k-1 + Cn-1,k = (n - k)!(k - 1)! + (n - k)!(k - 1)!

36

CHAPTER 2. COMBINATORIAL PROBABILITY

Factoring out the parts common to the two fractions

(n - 1)! =

(n - k - 1)!(k - 1)! (n - 1)!

= (n - k - 1)!(k - 1)!

11 +

n-k k

n

n!

=

(n - k)k (n - k)!k!

which proves (2.6). Binomial theorem.

The numbers in Pascal's triangle also arise if we take powers of (x + y):

(x + y)2 = x2 + 2xy + y2

(x + y)3 = (x + y)(x2 + 2xy + y2) = x3 + 3x2y + 3xy2 + y3

(x + y)4 = (x + y)(x3 + 3x2y + 3xy2 + y3) = x4 + 4x3y + 6x2y2 + 4xy3 + y4

or in general

n

(x + y)n =

Cn,mxmyn-m

m=0

To see this consider (x + y)5 and write it as

(2.7)

(x + y)(x + y)(x + y)(x + y)(x + y)

Since we can choose x or y from each parenthesis, there are 25 terms in all. If we want a term of the form x3y2 then in 3 of the 5 cases we must pick x, so there are C5,3 = (5 ? 4)/2 = 10 ways to do this. The same reasoning applies to the other terms, so we have

(x + y)5 = C5,5x5 + C5,4x4y + C5,3x3y2 + C5,2x2y3 + C5,1xy4 + C5,0y5 = x5 + 5x4y + 10x3y2 + 10x2y3 + 5xy4 + y5

Poker. In the game of poker the following hands are possible; they are listed in increasing order of desirability. In the definitions the word value refers to A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, or 2. This sequence also describes the relative ranks of the cards, with one exception: an Ace may be regarded as a 1 for the purposes of making a straight. (See the example in (d), below.)

(a) one pair: two cards of equal value plus three cards with different values J J 9 Q 3

(b) two pair: two pairs plus another card with a different value J J 9 9 3

(c) three of a kind: three cards of the same value and two with different values