Page 448 - Discrete Mathematics and Its Applications

6.5 Generalized Permutations and Combinations 427

TABLE 1 Combinations and Permutations With
and Without Repetition.
Type Repetition Allowed? Formula
n!
r-permutations No
(n − r)!
n!
r-combinations No
r! (n − r)!
r-permutations Yes n r
(n + r − 1)!
r-combinations Yes
r! (n − 1)!

EXAMPLE 6 What is the value of k after the following pseudocode has been executed?

k := 0
for i 1 := 1 to n
for i 2 := 1 to i 1
·
·
·
for i m := 1 to i m−1
k := k + 1

Solution: Note that the initial value of k is 0 and that 1 is added to k each time the nested loop
is traversed with a sequence of integers i 1 ,i 2 ,...,i m such that

1 ≤ i m ≤ i m−1 ≤ ··· ≤ i 1 ≤ n.

The number of such sequences of integers is the number of ways to choose m integers from
{1, 2,...,n}, with repetition allowed. (To see this, note that once such a sequence has been
selected, if we order the integers in the sequence in nondecreasing order, this uniquely defines
an assignment of i m ,i m−1 ,...,i 1 . Conversely, every such assignment corresponds to a unique
unordered set.) Hence, from Theorem 2, it follows that k = C(n + m − 1,m) after this code
has been executed. ▲

The formulae for the numbers of ordered and unordered selections of r elements, chosen
with and without repetition allowed from a set with n elements, are shown in Table 1.

Permutations with Indistinguishable Objects

Some elements may be indistinguishable in counting problems. When this is the case, care must
be taken to avoid counting things more than once. Consider Example 7.
EXAMPLE 7 How many different strings can be made by reordering the letters of the word SUCCESS?

Solution: Because some of the letters of SUCCESS are the same, the answer is not given by the
number of permutations of seven letters. This word contains three Ss, two Cs, one U, and one E.
To determine the number of different strings that can be made by reordering the letters, first note
that the three Ss can be placed among the seven positions in C(7, 3) different ways, leaving four