Mathematics for Computer Science

15.3. The Generalized Product Rule 453 Thus, the length-six passwords are in the setFS^5 , the length-seven passwords are inF  ...

Chapter 15 Cardinality Rules454 Prizes fortruly exceptionalCoursework Given everyone’s hard work on this material, the instructo ...

15.3. The Generalized Product Rule 455 15.3.1 Defective Dollar Bills A dollar bill isdefectiveif some digit appears more than on ...

Chapter 15 Cardinality Rules456 (^8) 0Z0Z0Z0Z (^7) Z0Z0m0Z0 (^6) 0Z0Z0Z0Z (^5) Z0Z0Z0Z0 (^4) 0a0Z0Z0Z (^3) Z0Z0Z0Z0 (^2) 0Z0Z0o0 ...

15.4. The Division Rule 457 3ŠD 6 permutations of the 3-element setfa;b;cg, which is the number we found above. Permutations wil ...

Chapter 15 Cardinality Rules458 (^8) 0Z0Z0Z0s (^7) Z0Z0Z0Z0 (^6) 0Z0Z0Z0Z (^5) Z0Z0Z0Z0 (^4) 0Z0Z0Z0Z (^3) Z0Z0Z0Z0 (^2) 0Z0Z0Z0 ...

15.4. The Division Rule 459 "! # k^1 k 2 k 3 k 4 "! # k^3 k 4 k 1 k 2 So a seating is determined by the sequence of knights goin ...

Chapter 15 Cardinality Rules460 15.5 Counting Subsets How manyk-element subsets of ann-element set are there? This question aris ...

15.6. Sequences with Repetitions 461 But we know there arenŠpermutations of ann-element set, so by the Division Rule, we conclud ...

Chapter 15 Cardinality Rules462 We can generalize this to splits into more than two subsets. Namely, letAbe ann-element set andk ...

15.7. The Binomial Theorem 463 From this bijection and the Subset Split Rule, we conclude that the number of ways to rearrange t ...

Chapter 15 Cardinality Rules464 by the Bookkeeper Rule. Hence, the coefficient ofankbkis n k
. So fornD 4 , this means: .aCb/^ ...

15.8. A Word about Words 465 15.8 A Word about Words Someday you might refer to the Subset Split Rule or the Bookkeeper Rule in ...

Chapter 15 Cardinality Rules466 15.9.1 Hands with a Four-of-a-Kind AFour-of-a-Kindis a set of four cards with the same rank. How ...

15.9. Counting Practice: Poker Hands 467 The rank of the triple, which can be chosen in 13 ways. The suits of the triple, which ...

Chapter 15 Cardinality Rules468 Thus, it might appear that the number of hands with Two Pairs is: 13
4 2 !
12
4 2 !
11
...

15.9. Counting Practice: Poker Hands 469 (Sometimes different approaches give answers thatlookdifferent, but turn out to be the ...

Chapter 15 Cardinality Rules470 For example, the hand above is described by the sequence: .7;K;A;2;};3/$f 7 }; K|; A~; 2; 3}g: ...

15.10. Inclusion-Exclusion 471 15.10.1 Union of Two Sets For two sets,S 1 andS 2 , theInclusion-Exclusion Ruleis that the size o ...

Chapter 15 Cardinality Rules472 ThenjM\EjD 4 C 2 ,jM\PjD 3 C 2 ,jE\PjD 11 C 2 , andjM\E\PjD 2. Plugging all this into the formul ...