Permutations and Combinations

The formulae for the numbers of permutations and combinations are useful for counting the number of simple events in many practical prob­lems.

DEFINITION 2.3.1 The number of permutations of taking r elements from n elements is the number of distinct ordered sets consisting of r distinct elements which can be formed out of a set of n distinct elements and is denoted by P".

For example, the permutations of taking two numbers from the three numbers 1, 2, and3 are (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2); therefore, we have P = 6.

THEOREM 2.3.1 P" = n/(n — r)l, where n reads n factorial and denotes n(n — 1) (n — 2) • • ■ 2 • 1. (We define 0! = 1.)

Proof. In the first position we can choose any one of n elements and in the second position n — 1 and so on, and finally in the rth position we can choose one of n — r + 1 elements. Therefore, the number of permu­tations is the product of all these numbers. □

DEFINITION 2.3.2 The number of combinations of taking r elements from n elements is the number of distinct sets consisting of r distinct elements which can be formed out of a set of n distinct elements and is denoted by Cnr.

Note that the order of the elements matters in permutation but not in combination. Thus in the example of taking two numbers from three, (1, 2) and (2, 1) make the same combination.

image002 Подпись: n (n — r) rl

THEOREM 2.3.2

Proof. It follows directly from the observation that for each combina­tion, r! different permutations are possible. □

EXAMPLE 2.3.3 Compute the probability of getting two of a kind and three of a kind (a “full house”) when five dice are rolled.

Let щ be the number on the ith die. We shall take as the sample space the set of all the distinct ordered 5-tuples {щ, n%, Щ, Щ, Щ), so that n(S) = 6 Let the ordered pair (г, j) mean that і is the number that appears twice and j is the number that appears three times. The number of the distinct ordered pairs, therefore, is P. Given a particular (г, j), we can choose two dice out of five which show i: there are c ways to do so. Therefore we conclude that the desired probability P is given by

P ■ c

P = 2 . 2 = 0.03858.

65

EXAMPLE 2.3.4 If a poker hand of five cards is drawn from a deck, what is the probability that it will contain three aces?

We shall take as the sample space the set of distinct poker hands without regard to a particular order in which the five cards are drawn. Therefore, n{S) = СІ2. Of these, the number of the hands that contain three aces but not the ace of clubs is equal to the number of ways of choosing the two remaining cards out of the 48 nonaces: namely, C2 . We must also count the number of the hands that contain three aces but not the ace of spades, which is also Cf, and similarly for hearts and diamonds. There­fore, we must multiply cf by four. The desired probability P is thus given by

Подпись:4Cf _ 94

Cf 54145

In Example 2.5.1 we shall solve the same problem in an alternative way.

Leave a reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>