The Art and Craft of Problem Solving

190 CHAPTER 6 COMBINATORICS

The Mississippi formula involves both multiplication and division. Let's examine

the role of each operation carefully, with the example of "PARADOXICAL." If all of

the letters were different, then there would be nine possible choices for the first letter,

eight for the second, seven for the third, etc., yielding a total of

9 x 8 x 7 x ... x I = 9!

different possible permutations. We multiplied the numbers because we were counting

ajoint event composed of nine sub-events, respectively, with 9,8,7 , ... , I choices. But

the letters are not all different; there are three indistinguishable A's. Hence the value 9!

has overcounted what we want. Pretend for a moment that we can distinguish the A's

by labeling them AI, A 2 , A 3. Then, for example, we would count CA 1 LPORA 2 A 3 XID

and CA 3 LPORAIA 2 XID as two different words, when they are really indistinguish­

able. We want to count the word CALPORAAXID just once, but we will count it

3! = 6 times since there are 3! ways of permuting those three A's. In other words, we

are uniformly overcounting by a factor of 3!, and can rectify this by dividing by 3!.

That is why the correct answer is^1 3V, In general,

To count the number of ways a joint event occurs, multiply together the

number of choices for each sub-event. To rectify uniform overcounting,

divide by the overcounting factor.

6.1.11 Let's apply the Mississippi formula to an n-letter string consisting of r Os and

(n - r) Is (also known as an n-bit string). Verify that the number of permutations

would be

n!

r!(n- r)!'

This is often denoted by (�) ("n choose r") and is also called a binomial coefficient.

For example, the number of distinct permutations of "000 0111 " is G) = 3T�! = 35.

6.1.12 Combinations of n things taken r at a time. Here is a seemingly different

problem: We are ordering a pizza, and there are eight different toppings available (an­

chovies, garlic, pineapple, sausage, pepperoni, mushroom, olive, and green pepper).

We would like to know how many different pizzas can be ordered with exactly three

toppings. In contrast to permutations, the order that we choose the toppings does not

matter. For example, a "sausage-mushroom-garlic" pizza is indistinguishable from a

"mushroom-garlic-sausage" pizza.

To handle this difficulty, we proceed as we did with the Mississippi problem. If the

order did matter, then the number of different pizzas would be the simple permutation

P(8, 3), but then we are uniformly overcounting by a factor of3!. So the correct answer

IS

Notice that

P(8,3)

3!

P(8, 3)

=

�

=

( 8 )

.

3! 5!3! 3