Page 444 - Discrete Mathematics and Its Applications

6.5 Generalized Permutations and Combinations 423

Although infinitely many sequences start with a specified c) 1, 2, 6, 20, 70, 252, 924, 3432, 12870, 48620,...
set of terms, each of the following lists is the start of a d) 1, 1, 2, 3, 6, 10, 20, 35, 70, 126,...
sequence of the type desired.] e) 1, 1, 1, 3, 1, 5, 15, 35, 1, 9,...
a) 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66,... f) 1, 3, 15, 84, 495, 3003, 18564, 116280, 735471,
b) 1, 4, 10, 20, 35, 56, 84, 120, 165, 220,... 4686825,...

6.5 Generalized Permutations and Combinations

Introduction

In many counting problems, elements may be used repeatedly. For instance, a letter or digit may
be used more than once on a license plate. When a dozen donuts are selected, each variety can
be chosen repeatedly. This contrasts with the counting problems discussed earlier in the chapter
where we considered only permutations and combinations in which each item could be used at
most once. In this section we will show how to solve counting problems where elements may
be used more than once.
Also, some counting problems involve indistinguishable elements. For instance, to count the
number of ways the letters of the word SUCCESS can be rearranged, the placement of identical
letters must be considered. This contrasts with the counting problems discussed earlier where all
elements were considered distinguishable. In this section we will describe how to solve counting
problems in which some elements are indistinguishable.
Moreover, in this section we will explain how to solve another important class of counting
problems, problems involving counting the ways distinguishable elements can be placed in
boxes. An example of this type of problem is the number of different ways poker hands can be
dealt to four players.
Taken together, the methods described earlier in this chapter and the methods introduced
in this section form a useful toolbox for solving a wide range of counting problems. When the
additional methods discussed in Chapter 8 are added to this arsenal, you will be able to solve a
large percentage of the counting problems that arise in a wide range of areas of study.

Permutations with Repetition

Counting permutations when repetition of elements is allowed can easily be done using the
product rule, as Example 1 shows.

EXAMPLE 1 How many strings of length r can be formed from the uppercase letters of the English alphabet?

Solution: By the product rule, because there are 26 uppercase English letters, and because each
r
letter can be used repeatedly, we see that there are 26 strings of uppercase English letters of
length r. ▲

The number of r-permutations of a set with n elements when repetition is allowed is given
in Theorem 1.

r
THEOREM 1 The number of r-permutations of a set of n objects with repetition allowed is n .

Proof: There are n ways to select an element of the set for each of the r positions in the
r-permutation when repetition is allowed, because for each choice all n objects are available.
r
Hence, by the product rule there are n r-permutations when repetition is allowed.