Discrete Mathematics for Computer Science

454 CHAPTER 7 Counting and Combinatorics

The result just given is a generalization of the case in which all n letters of the per-

mutation are distinguishable, since in that case, the denominator consists of 1! occurring n

times.

The following examples will show how to count the number of permutations when

some elements are not distinguishable among themselves, like repeated letters in a word.

Example 1. How many permutations are there of the letters in the word excellent?

Solution. The letter e occurs three times, and the letter I occurs twice. Each of the remain-

ing letters x, c, n, and t occurs once. By Theorem 1, the number of such permutations is

9!

P(9; 3, 2, 1, 1, 1, 1) 3!2 3-- 17 1! 1! 1!

= 30,240 U

Example 2. How many four-letter words can be formed using the letters a, a, a, b, b, c,

c, c, c, d, d?

Solution. The first step in finding the required count is to decompose the problem into a

number of disjoint subcases. Theorem 1 can be used on each subcase, and the final answer

is found by using the Addition Principle with the answers for the subcases. A description

of the subcases and the count for each subcase are given in Table 7.5.

Table 7.5 Subcases for Example 2

Subcases

Kinds of Letter No. of Choices for Letters No. of Arrangements for Letters

(a) 4-same C(1, 1) P(4; 4)

(b) 3-same C(2, 1) P(4; 3, 1)

1--different C(3, 1)

(c) 2-pairs C(4,2 2) P(4; 2, 2)

(d) 2-same C(4, 1) P(4; 2, 1, 1)

2-different C(3, 2)

(e) 4--different C(4, 4) P(4; 1, 1, 1, 1)

# Using the Addition Principle, the final answer is

# Words = C(1, 1) • P(4; 4) + C(2, 1) • C(3, 1) -P(4; 3, 1) + C(4, 2) .P(4; 2, 2)

+ C(4, 1) .C(3, 2) .P(4; 2, 1, 1) + C(4, 4) .P(4; 1, 1, 1, 1)

= 1 + 2.3.4 + 6.6 + 12 + 1.2.3.4

= 229 U

When the partitions consist of sets of fixed size and the sizes are not all distinct, we

must take into account that the elements of the partition can be permuted among themselves

without changing the count that is needed.

Example 3. In how many ways can 12 examinations be split into three sets of four ex-

aminations each?