Discrete Mathematics for Computer Science

Counting with Repeated Objects 453

We see that the answer is the same in both cases. In general, the order in which letters

are assigned locations will not affect the answer, since we only use the number of such

cases.

This example is a special case of the theorem stated below that gives the number of

permutations of n letters with repetitions allowed. In this case, we have sets of distinguish-

able objects, but the objects within each set are indistinguishable from one another.

Definition 1. Let ml1, m2 • , Ink be distinct symbols. Let a set of n symbols consist of

ri copies of mi for I < i < k such that Ek=I ri = n. The number of permutations with

repetitions using these n symbols is denoted as P (n; , r2 .... rm).

In the notation given by Definition 1, the terms ri for 1 < i < k are not assumed to be

in any particular order. Observe that P(n, r) and P(n; r) represent very different ideas.

Theorem 1. Let n = rl + r2 + •.. + rk be any sum of positive integers. The number of

ways to arrange rl objects of type 1, r2 objects of type 2. and rk objects of type k is

given by

P(n; ri, r2. rk) = C(n, ri) • C(n - rl, r2) ... C(n - r ... rk-1, rk)

n!

rl!r2! .. rk!

Proof. The proof is by induction on n. Let no = 1 and r, + r2 + .+ + rk = n. Define

n!

T = {n : P(n; rl, r2 ... , rk) = rl!

r2!. .rk!

(Base step) The base case is 1. We leave that case to the reader.

(Inductive step) Let n > no. Assume that for all m where no < m < n, m e T. Now,

prove that n E T.

The number P(n; r, r2 ..... rk) is, by definition, the number of ways that n letters

can be arranged if ri of the letters are the same for^1 < i < k.

Choose rl of these locations for occurrences of the first letter. This can be done in

n!

C(n, ) = Trl! (n - rl)!

ways. After any choice of r, locations, there are n - rl locations remaining to be filled by

the k - 1 other letters. There are P(n - rl; r2, r3 .... T rk) ways to arrange the remaining

letters, and, since no < n - rl < n, by the inductive hypothesis

(n - rI)!

P (n - ri; r2, r3, .... rk) = -!r2! ( ... rk!

It follows from the Multiplication Principle that

P(n; ri, r2. rk) = C(n, rl) • P(n - rl; r2, r3... rk)

n! (n - rl)!

rl!(n- rl)! r2! ... rk!

n!

ri!, r2! ... rk!

Thus, n e T. Therefore, by the Strong Form of Mathematical Induction, T {n e N:

n > 1). U