Study Guides for Discrete Mathematics

Section 4.3 - Permutations and Combinations

Permutations

A permutation is an arrangement of objects. Permutation formulas enable us to count the number of permutations for a set of objects.

Example: How many arrangements are there for the colors Red, Green and Blue?

There are several means of solving this problem.

First, we may simply list all of the possibilities:

(RGB, RBG, GRB, GBR, BRG, BGR). Thus we see that there are six.

Second, we may reason that we may select one of 3 colors to fill the first slot, one of the two remaining colors to fill the second slot, thus leaving only one to fill the third slot. So by the PRODUCT rule we find that the number of arrangements is 3· 2· 1 = 6. You may have already reasoned that this approach may be extended to show that the number of ways of arranging N objects is N!.

Observe that in the above example we made some subtle assumptions.

  1. No color may be repeated and
  2. Each arrangement uses all colors (objects).

We shall find that often we need to modify our computations to account for exceptions to the above assumptions.

 

Permutation Computation Theorem

R of N objects may be arranged in N!/(N-R)! ways.

Another way of stating the above Theorem is "The number of permutations of N objects taken R at a time is N!/(N-R)!."

We may denote the number of permutations of N objects taken R at a time by P(N, R).

Example: In how many ways can we arrange two of the four seasons (Wi, Sp, Su, Fa)?

4!/(4-2)! = 4!/2! = 4· 3 = 12.

(Wi, Sp), (Wi, Su), (Wi, Fa),

(Sp, Wi), (Sp, Su), (Sp, Fa),

(Su, Wi), (Su, Sp), (Su, Fa),

(Fa, Wi), (Fa, Sp), (Fa, Su).

 

Combinations

Observe that in the above example, (Wi, Sp) is considered to be a different arrangement than (Sp, Wi). Often we wish to count only the number of ways R objects can be selected from N objects. Such a computation in called a Combination. In this case, (Wi, Sp) and (Sp, Wi) are considered to be the same. We may compute this by first computing the Permutations and "dividing out" the repetitions. In the example above we observe that each arrangement (such as (Wi, Sp)) has a mate ((Sp, Wi)). Therefore, we may, in this case, divide the number of permutations (12) by 2 and determine that there are 6 combinations of the four seasons taken two at a time. In general the number of repetitions which need to be divided out equals R!.

 

Example: A Computer Science course is to be scheduled to meet twice a week between Monday and Friday. In how many ways may we select the two meeting days?

The number of permutations of two days selected from 5 days equals 5!/(5-2)! = 5!/3! = 5· 4 = 20.

Since selecting, for example, Monday, Thursday is equivalent to selecting Thursday, Monday we must determine the number of combinations (rather than permutations) by dividing the number of permutations by 2!.

20/2! = 10.

 

Combination Computation Theorem

The number of combinations of N objects taken R at a time is P(N, R)/R! = N!/(R!· (N-R)!).

We may denote the combination of N objects taken R at a time by C(N, R).