6.1 INTRODUCTION TO COUNTING 1896.1.4 Let A and B be finite sets that are disjoint (A n B = 0). Then 6.1.2 is equivalent
to the statement
IAUBI = IAI+IBI·
6.1. 5 Notice that 6.1.3 is equivalent to the statement
IA xBI = IAI·IBI,
for any two finite sets A and B (not necessarily disjoint).
6.1.6 A permutation of a collection of objects is a reordering of them. For example,
there are six different permutations of the letters ABC, namely ABC, ACB, BAC,
BCA, CAB, CBA. There are 5 ·4·3·2· 1 = 120 different ways to permute the letters in
"HARDY." You probably know that n· (n -1 )···^1 is denoted by the symbol n!, called
"n factorial." You should learn (at least passively) the values of n! for n :::; 10. (While
you are at it, learn the first dozen or so of all the common sequences: squares, cubes,
Fibonacci, etc.)6.1.7 Permutations of n things taken r at a time. The number of different three-letter
words we could make using the nine letters in "CHERNOBYL" is 9. 8. 7 = 504. In
general, the number of distinct ways of permuting r things chosen from n things is
n.(n - l) ... (n- r+l). 1
This product is also equal to
(n :
!
r)!and is denoted by P(n,r).6.1. 8 But what about permutinp the letters in "GAUSS"? At first you might think the
answer is 5!, but it is actually �. Why?
6.1.9 Furthermore, explain that the number of different permutations of "PARADOX
ICAL" is IJ!, not I�!. Why?
6.1.10 Likewise, verify that "RAMANUJAN" has ii different permutations. State a
general formula. Check with small numbers to make sure that your formula works.
We shall call the formula you got in Problem 6.1.10 the Mississippi formula,
since an amusing example of it is computing the number of permutations in "MISSIS
SIPPI," which is, of course, 4 Mi!. The Mississippi formula is easy to remember by
doing examples, but let's write it out formally. This is a good exercise in notation and
also helps clarify just what we are counting. Here goes:
We are given a collection of balls that are indistinguishable except fo r
color. If there are ai balls of color i,for i = 1,2, ... ,n, then the number
of diff erent ways that these balls can be arranged in a row is
(al + a 2 + ... + an)!
al !a 2 !" ·an!
1 Notice that the product ends with (n -r+ I) and not (n -r). This is a frequent source of minor errors, known
to computer programmers as "OBOB," the "off-by-one bug."