15.3. The Generalized Product Rule 453
Thus, the length-six passwords are in the setFS^5 , the length-seven passwords
are inF S^6 , and the length-eight passwords are inFS^7. Since these sets
are disjoint, we can apply the Sum Rule and count the total number of possible
passwords as follows:
j.FS^5 /[.FS^6 /[.FS^7 /j
DjFS^5 jCjFS^6 jCjFS^7 j Sum Rule
DjFjjSj^5 CjFjjSj^6 CjFjjSj^7 Product Rule
D 52 625 C 52 626 C 52 627
1:8 1014 different passwords:
15.3 The Generalized Product Rule
In how many ways can, say, a Nobel prize, a Japan prize, and a Pulitzer prize be
awarded tonpeople? This is easy to answer using our strategy of translating the
problem about awards into a problem about sequences. LetPbe the set ofnpeople
taking the course. Then there is a bijection from ways of awarding the three prizes
to the setP^3 WWDPPP. In particular, the assignment:
“Barak wins a Nobel, George wins a Japan, and Bill wins a Pulitzer prize”
maps to the sequence.Barak;George;Bill/. By the Product Rule, we havejP^3 jD
jPj^3 Dn^3 , so there aren^3 ways to award the prizes to a class ofnpeople. Notice
thatP^3 includes triples like.Barak;Bill;Barak/where one person wins more than
one prize.
But what if the three prizes must be awarded todifferentstudents? As before,
we could map first assignment to the triple.Bill;George;Barak/ 2 P^3. But this
function isno longer a bijection. For example, no valid assignment maps to the
triple.Barak;Bill;Barak/because now we’re not allowing Barak to receive two
prize. However, thereisa bijection from prize assignments to the set:
SDf.x;y;z/ 2 P^3 jx,y, andzare different peopleg
This reduces the original problem to a problem of counting sequences. Unfortu-
nately, the Product Rule does not apply directly to counting sequences of this type
because the entries depend on one another; in particular, they must all be different.
However, a slightly sharper tool does the trick.
