Mathematics for Computer Science
14.8. The Pigeonhole Principle 573 1 st^ sock A f 2 nd^ sock 3 rd^ sock 4 th^ sock red B green blue Figure 14.3 One possible map ...
Chapter 14 Cardinality Rules574 14.8.1 Hairs on Heads There are a number of generalizations of the pigeonhole principle. For exa ...
14.8. The Pigeonhole Principle 575 0020480135385502964448038 3171004832173501394113017 5763257331083479647409398 824733100004299 ...
Chapter 14 Cardinality Rules576 On the other hand: jBjD 90 1025 C 1 0:901 1027 : Both quantities are enormous, butjAjis a bi ...
14.8. The Pigeonhole Principle 577 14.8.3 A Magic Trick A Magician sends an Assistant into the audience with a deck of 52 cards ...
Chapter 14 Cardinality Rules578 f 8 ~;K;Q;2};6}g f 8 ~;K;Q;9|;6}g fK;8~;6};Qg fK;8~;Q;2}g f 8 ~;K;Q;2}g ...
14.8. The Pigeonhole Principle 579 Using the matching, the Magician sees that the hand (14.3) is matched to the se- quence (14.4 ...
Chapter 14 Cardinality Rules580 A 2 3 4 5 6 8 7 9 10 J Q K Figure 14.6 The 13 card ranks arranged in cyclic order. The suit of ...
14.9. Inclusion-Exclusion 581 The Magician starts with the first card, 10 ~, and hops 6 ranks clockwise to reach 3 ~, which is ...
Chapter 14 Cardinality Rules582 departments? LetMbe the set of math majors,Ebe the set of EECS majors, and Pbe the set of physic ...
14.9. Inclusion-Exclusion 583 Remarkably, the expression on the right accounts for each element in the union of S 1 ,S 2 , andS ...
Chapter 14 Cardinality Rules584 First, we must determine the sizes of the individual sets, such asP 60. We can use a trick: grou ...
14.9. Inclusion-Exclusion 585 The formulas for unions of two and three sets are special cases of this general rule. This way of ...
Chapter 14 Cardinality Rules586 Rule(Inclusion-Exclusion-II). ˇˇ ˇˇ ˇ [n iD 1 Si ˇˇ ˇˇ ˇ D X ;¤If1;:::;ng .1/jIjC^1 ˇˇ ˇˇ ˇ \ i ...
14.10. Combinatorial Proofs 587 for any nonempty setIŒ1::mç. This lets us calculate: jSjD ˇˇ ˇ ˇˇ [m iD 1 Cpi ˇˇ ˇ ˇˇ (by (14.8 ...
Chapter 14 Cardinality Rules588 But we didn’t really have to resort to algebra; we just used counting principles. Hmmm.... 14.10 ...
14.10. Combinatorial Proofs 589 Lemma 14.10.1(Pascal’sTriangle Identity). n k ! D n 1 k 1 ! C n 1 k ! : (14.10) We provedPascal’ ...
Chapter 14 Cardinality Rules590 Now we’ve already countedSone way, via the Bookkeeper Rule, and found jSjD n k . The other “wa ...
14.11. References 591 n-element subsets. From another perspective, the number of hands with exactlyrred cards is n r ! 2n nr ! s ...
Chapter 14 Cardinality Rules592 Problem 14.2. In how many different ways is it possible to answer the next chapter’s practice pr ...
«
25
26
27
28
29
30
31
32
33
34
»
Free download pdf