452 CHAPTER 7 Counting and Combinatorics
objects are identical and not distinguishable, as in this case. Sections 7.8-7.10 explain
methods for handling such situations as well as introducing combinatorial identities. In
Section 7.10, a representation of the binomial coefficients known as Pascal's triangle is
also introduced and used to prove several useful combinatorial identities.7.8.1 Permutations with Repetitions
A typical problem that motivates how to count permutations of objects not necessarily
all distinct-or permutations with repetitions-is the problem of counting the number of
permutations of the letters in a word with repeated letters. As an example, let us determine
the number of distinguishable permutations of the letters in the word abracadabra. The
letter a is repeated five times, the letter b two times, the letter r two times, and the letters
c and d just once each. A permutation of these 11 letters can be constructed as follows:
Pick 5 of the 11 positions for the letters of this word, and assign them the letter a. This can
be done in C(1 1, 5) different ways. Of the remaining six letter positions, choose two of
these positions for the occurrences of the letter b. This can be done in C(6, 2) ways. Now,
choose two of the remaining letter positions for the occurrences of the letter r. This can be
done in C(4, 2) ways. Choose one of the two remaining letter positions for the occurrence
of the letter c. This can be done in C(2, 1) ways. Put d in the letter position remaining. By
the Multiplication Principle, the total number of arrangements will be the product of the
number of ways of assigning each of the different letters.(# Permutations of the letters of abracadabra)
= C(l1, 5). C(6, 2). C(4, 2). C(2, 1). C(1, 1)
11! 6! 4! 2! 1!
6!5! 4!2! 2!2! 1!1! 1!0!
11!
5!2!2! 1! 1!
11!
5!2!2!
83,160When the binomial coefficients are replaced with their factorial equivalents, many of the
factors cancel. The terms remaining in the denominator represent the number of times that
each letter is repeated in the permutation.
A question that should arise here is whether it makes any difference in what order let-
ters are assigned places. For example, suppose the abracadabra problem is solved by plac-
ing the occurrences of r first, c second, a third, b fourth, and d fifth. The answer would be(# Permutations of the letters of abracadabra)= C(ll, 2)- C(9, 1)- C(8, 5)- C(3, 2). C(l, 1)
11! 9! 8! 3! 1!
9!2! 8!1! 3!5! 2!1! 1!0!
11!
5!2!2! 1! 1!
11!
5! 2! 2!
= 83,160