Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

92 TECHNIQUES OF COUNTING [CHAP. 5

Corollary 5.5: There aren! permutations ofnobjects (taken all at a time).

For example, there are 3!=6 permutations of the three lettersA,B,C. These are:

ABC, ACB, BAC, BCA, CAB, CBA.

Permutations with Repetitions

Frequently we want to know the number of permutations of a multiset, that is, a set of objects some of which
are alike. We will let

P(n;n 1 ,n 2 , ..., nr)

denote the number of permutations ofnobjects of whichn 1 are alike,n 2 are alike,...,nrare alike. The general
formula follows:

Theorem 5.6: P(n;n 1 ,n 2 ,..., nr)=

n!
n 1 !n 2 !...nr!
We indicate the proof of the above theorem by a particular example. Suppose we want to form all possible
five-letter “words” using the letters from the word “BABBY.” Now there are 5!=120 permutations of the objects
B 1 ,A,B 2 ,B 3 ,Y, where the threeB’s are distinguished. Observe that the following six permutations

B 1 B 2 B 3 AY,B 2 B 1 B 3 AY,B 3 B 1 B 2 AY,B 1 B 3 B 2 AY,B 2 B 3 B 1 AY,B 3 B 2 B 1 AY

produce the same word when the subscripts are removed. The 6 comes from the fact that there are 3!=3·2·1= 6
different ways of placing the threeB’s in the first three positions in the permutation. This is true for each set of
three positions in which theB’s can appear. Accordingly, the number of different five-letter words that can be
formed using the letters from the word “BABBY” is:

P( 5 ; 3 )=

5!

3!

= 20

EXAMPLE 5.5 Find the numbermof seven-letter words that can be formed using the letters of the word
“BENZENE.”

We seek the number of permutations of 7 objects of which 3 are alike (the threeE’s), and 2 are alike (the two
N’s). By Theorem 5.6,

m=P( 7 ; 3 , 2 )=

7!

3! 2!

=

7 · 6 · 5 · 4 · 3 · 2 · 1

3 · 2 · 1 · 2 · 1

= 420

Ordered Samples

Many problems are concerned with choosing an element from a setS, say, withnelements. When we choose
one element after another, say,rtimes, we call the choice anordered sampleof sizer. We consider two cases.

(1) Sampling with replacement

Here the element is replaced in the setSbefore the next element is chosen. Thus, each time there arenways
to choose an element (repetitions are allowed). The Product rule tells us that the number of such samples is:

n·n·n···n·n(rfactors)=nr