ing ll 1 The generalized Product Rule What if the three prizes must be awarded to different students? As before, we could map the assignment person a wins prize #1, y wins prize #2, and z wins prize #3 to the triple (a, 3, a)EPx PX P. But this function is no longer a bijection. For exampl no valid assignment maps to the triple(Dave, Dave, Becky) because Dave is not allowed to receive two awards. However, there is a bijection from prize assignments to the set S=i(a, y,z)EPXPXPIa, y, and z are different people) This reduces the original problem to a problem of counting sequences. Unfortunately, the Product Rule is of no help in 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 Rule 1(Generalized Product Rule). Let s be a set of length-k sequences. If there are . n1 possible first entries, n2 possible second entries for each first entry, n3 possible third entries for each combination of first and second entries, etc. tHh Sl=m1:m2·m3…mk In the awards example, S consists of sequences(a, y, z). There are n ways to choose r, the recipient of prize #1. For each of these, there are n-1 ways to choose y, the recipient of prize #2, since everyone except for person r is eligible. For each combination of a and y, there are n-2 ways to choose z, the recipient of prize #3, because everyone except for and y is eligible. Thus, according to the generalized Product Rule, there are Sl=n·(mn-1)·(n-2) ways to award the 3 prizes to different people 1.1 Defective dollars A dollar is defective some digit appears more than once in the 8-digit serial number. If you check your wallet, youll be sad to discover that defective dollars are all-too-common2 Counting II 1 The Generalized Product Rule What if the three prizes must be awarded to different students? As before, we could map the assignment “person x wins prize #1, y wins prize #2, and z wins prize #3” to the triple (x, y, z) ∈ P × P × P. But this function is no longer a bijection. For example, no valid assignment maps to the triple (Dave, Dave, Becky) because Dave is not allowed to receive two awards. However, there is a bijection from prize assignments to the set: S = {(x, y, z) ∈ P × P × P x| , y, and z are different people} This reduces the original problem to a problem of counting sequences. Unfortunately, the Product Rule is of no help in 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. Rule 1 (Generalized Product Rule). Let S be a set of length­k sequences. If there are: • n1 possible first entries, • n2 possible second entries for each first entry, • n3 possible third entries for each combination of first and second entries, etc. then: | | S = n1 · n2 · n3 · · · nk In the awards example, S consists of sequences (x, y, z). There are n ways to choose x, the recipient of prize #1. For each of these, there are n − 1 ways to choose y, the recipient of prize #2, since everyone except for person x is eligible. For each combination of x and y, there are n − 2 ways to choose z, the recipient of prize #3, because everyone except for x and y is eligible. Thus, according to the Generalized Product Rule, there are | | S = n · (n − 1) · (n − 2) ways to award the 3 prizes to different people. 1.1 Defective Dollars A dollar is defective some digit appears more than once in the 8­digit serial number. If you check your wallet, you’ll be sad to discover that defective dollars are all­too­common