Discrete Mathematics for Computer Science

436 CHAPTER 7 Counting and Combinatorics

U Permutations and Combinations

In scientific experiments used to determine how well several nutrients interact to stimulate

plant growth, a sequence of different treatments may be proposed. The order in which the

treatments are performed may make a difference. To show whether the order of application

for the nutrients or the nutrients themselves is the important factor, all possible orders of

application must be known and tried. On the other hand, when a court system selects a

number of citizens to be in a jury pool, it is not important in what order citizens were

chosen, only that they were chosen. There are many fewer ways to select a jury pool of a

given size than there are ways to schedule the sequential application of the same number

of treatments in a scientific experiment. In this section, the Multiplication Principle is used

to count the number of possibilities for both kinds of problems.

7.5.1 Permutations

The first problem to consider here is how to count the number of possibilities when the

order of choice is important. We also consider that each of the elements being chosen is

distinguishable from all the other elements. Recognizing whether the elements that are

being arranged or counted or chosen are distinguished from one another is a key step in

deciding what formula is applicable.

Definition 1. Let n, r E N. A permutation of an n-element set is a linear ordering of

the n elements of the set. For n > r > 0 an r-permutation of an n-element set is a linear

ordering of r elements of the set.

Example 1. List all permutation of the elements a, b, and c.

Solution. The permutations are abc, acb, bac, bca, cab, and cba. U

Let P(n, r) denote the number of r-permutations of an n-element set. We define

P(n, 0) = 1 for all n E N.

Theorem 1. Let n > r > 0. Then, P(n, r) = n • (n - 1) -(n - 2)... (n - r +1).

Proof Theproofis by induction onn. Letno = 1. LetT = In EN : P(n,r) =n • (n -

1)...(n-r+l)forn>r >0}.

(Base step) There is only one way to arrange the one element of a one element set. Thus,

P(l, 1) = 1, and 1 E T.

(Inductive step) Let n > no, and assume n c T. Now, prove n ± 1 e T. That is, P(n +

1,r) = (n + 1)n... ((n + 1) - (r + 1)) for allr such that n > r > 0.

Let X be any set of n + 1 elements for which we must form an ordering of r of the

elements. Choose one element from X-say, x-to be the first element of the ordering.

This can be done in n + 1 ways. The problem remaining is to form an ordered arrangement

of r - 1 of the remaining n elements. By the inductive hypothesis, this can be done in

P(n, r - 1) ways. The total number of ways to form an ordered r-arrangement of a set

with n + 1 elements is (n + 1) • P(n, r - 1) = P(n + 1, r). Therefore, n + I E T.

By the Principle of Mathematical Induction, T = N - {0}. E