Statistics 510: Notes 4

Statistics 510: Notes 4

Reading: Sections 1.3-1.5, 2.5

Review from last class

For a sample space with equally likely outcomes, for any event ,

Generalized basic principle of counting: If r experiments that are to be performed are such that the first one may result in any of possible outcomes and if for each of these possible outcomes, there are possible outcomes of the second experiment, and if for each of the possible outcomes of the first two experiments, there are possible outcomes of the third experiment, and if ... then there is a total of possible outcomes of the r experiments.

We will now study some special applications of the generalized basic principle of counting.

I. Permutations (Section 1.3)

A permutation of a set of objects is an ordered arrangement of the objects.

For example, for the set of three letters a, b and c, there are six permutations: abc, acb, bac, bca, cab and cba . This result could be obtained from the generalized basic principle of counting: the first object in the permutation can be any of the 3, the second object in the permutation can then be chosen from any of the remaining 2, and the third object in the permutation is then chosen from the remaining 1. Thus there are 3*2*1=6 possible permutations.

Suppose now that we have n objects. Reasoning similar to that we have just used for the 3 letters shows that there are

different permutations of the n objects. We denote by (pronounced n factorial).

Example 1: How many different batting orders are possible for a baseball team consisting of 9 players?

Permutations can be combined with other experiments in applying the generalized basic principle of counting.

Example 2: A deck of 52 cards is shuffled and dealt face up in a row. In how many ways can the four aces be adjacent?

Stirling’s formula: Computing n! can be quite cumbersome, even for n’s that are fairly small – 16! is already in the trillions. Calculators can help for small n, but even their capacity is quickly exceeded. Fortunately, there is a fairly easy to use approximation: according to Stirling’s formula

Example:

16! = 2.092279e+13

=2.081411e+13

We shall now determine the number of permutations of a set of n objects when certain of the objects are indistinguishable from each other.

Example 3: How many different letter arrangements can be formed using the letters PEPPER?

Solution: We first note that there are 6! permutations of the letters P1E1P2P3E2R when the 3 P’s and the 2 E’s are distinguished from each other. However, consider any one of these permutations – for instance P1P2E1P3E2R. If we now permute the P’s among themselves and the E’s among themselves, then the resultant arrangement would still be of the form PPEPER. That is, all 3!*2! permutations

P1P2E1P3E2R P1P2E2P3E1R

P1P3E1P2E2R P1P3E2P2E1R

P2P1E1P3E2R P2P1E2P3E1R

P2P3E1P1E2R P2P3E2P1E1R

P3P1E1P2E2R P3P1E2P2E1R

P3P2E1P1E2R P3P2E2P1E1R

are of the form PPEPER. Hence there are 6!/(3!*2!)=60 possible letter arrangements of the letters PEPPER.

In general, the same reasoning as that of Example 3 shows that there are

different permutations of n objects, of which n1 are alike, n2 are alike, ..., nr are alike.

Example 4: How many different signals, each consisting of 9 flags hung in a line, can be made from a set of 4 white flags, 3 red flags and 2 blue flags if all flags of the same color are identical?

II. Combinations

Order is not always a meaningful characteristic of a collection of elements. Consider a poker player being dealt a five-card hand. Whether he receives a king of diamonds, 9 of diamonds, 7 of diamonds, 5 of diamonds, and 2 of diamonds in that order or in any of the other 5!-1 permutations of those particular five cards is irrelevant – the hand is still the same.

We call a collection of r unordered elements a combination of size r.

For example, consider how many different combinations of size 3 can be selected from the five items A, B, C, D and E.

First, consider the number of ways of selecting three items, where order matters. There are 5 ways of selecting the first item, then 4 ways of selecting the second item given the first item and then 3 ways of selecting third item given the first two items – hence, there are 5*4*3=60 ways of selecting three items in order. For counting the number of combinations of size 3, if we count the number of ways of selecting 3 items where order matters, we are counting each combination 6 times (that is, for the combination of letters A,B,C, all of the permuations ABC, ACB, BAC, BCA, CAB and CBA will be counted when order of selection is relevant). It follows that the number of combinations of size 3 is

In general, the number of combinations of size r from a group of n objects is

.

Notation and terminology: We define , for , by

By convention, 0!=1.

It often helps to think of combinations in the context of drawing objects out of an urn. If an urn contains n chips labeled 1 through n, the number of ways we can reach in and draw out different samples of size r is . In deference to this sampling interpretation for the formation of combinations, is usually read “n things taken r at a time” or “n choose r.”

Example 5: From a group of 5 women and 7 men, how many different committees consisting of 2 women and 3 men can be formed? What if 2 of the men are feuding and refuse to serve on the committee together?

III. Multinomial Coefficients

We consider the following problems: a set of n distinct items is to be divided into r distinct groups of respective sizes n1, n2,..., nr, where . How many different divisions are possible?

Example 6: A police department in a small city consists of 10 officers. If the department policy is to have 5 of the officers patrolling the streets, 2 of the officers working full time at the station, and 3 of the officers on reserve at the station, how many different divisions of the 10 officers into three groups are possible?

General solution: There are possible choices for the first group; for each choice of the first group, there are possible choices for the second group; for each choice of the first two groups, there are possible choices for the third group; and so on. Hence, it follows from the generalized version of the basic counting principle that there are

possible divisions.

We define .

Solution to Example 6: There are possible divisions.

IV. Return to Probability and Sample Spaces with Equally Likely Outcomes (Section 2.5)

Example 7: A committee of 5 is to be selected from a group of 6 men and 9 women. If the selection is made randomly, what is the probability that the committee consists of 3 men and 2 women.

Note: The committee being randomly selected means that each of the possible combinations is equally likely to be selected.

Example 8: An urn contains n balls, of which one is special. If k of these balls are withdrawn one at a time, with each selection being equally likely to be any of the balls that remain at the time, what is the probability that the special ball is chosen?

Example 9: A poker hand consists of 5 cards. If the cards have distinct consecutive values and are not all of the same suit, we say that the hand is a straight. For instance, a hand consisting of the five of spades, six of spades, seven of spades, eight of spades and nine of hearts is a straight? What is the probability that one is dealt a straight?

Example 10: A deck of 52 playing cards is well shuffled and the cards turned up one at a time until the first ace appears. Is the next card – that is, the card following the first ace – more likely to be the ace of spades or the two of clubs?

Example 11: A football team consists of 20 offensive and 20 defensive players. The players are to be paired in groups of 2 for the purpose of determining roommates. If the pairing is done at random, what is the probability that there are no offensive-defensive roommate pairs? What is the probability that there are 2i offensive-defensive roommate pairs, i=1,2,...,10?