Mathematics for Computer Science
15.10. Inclusion-Exclusion 473 AndjP 42 \P 04 j D8Šas well by a similar argument. Finally, note thatjP 60 \ P 04 \P 42 jD7Šby a ...
Chapter 15 Cardinality Rules474 These sums have alternating signs in the Inclusion-Exclusion formula, with the sum of thek-way i ...
15.10. Inclusion-Exclusion 475 We’ll be able to find the size of this union using Inclusion-Exclusion because the intersections ...
Chapter 15 Cardinality Rules476 prove some heavy-duty formulas without using any algebra at all. Just a few words and you are do ...
15.11. Combinatorial Proofs 477 All teams of the first type contain Ali, and no team of the second type does; therefore, the two ...
Chapter 15 Cardinality Rules478 by counting one way, and Oscar computed jSjD n k ! by counting another way. Equating these two e ...
15.12. The Pigeonhole Principle 479 Teaching Assistants. Here is another colorful example of a combinatorial argu- ment. Theorem ...
Chapter 15 Cardinality Rules480 1 st^ sock A f 2 nd^ sock 3 rd^ sock 4 th^ sock red B green blue Figure 15.3 One possible mappin ...
15.12. The Pigeonhole Principle 481 Here, the pigeons form setA, the pigeonholes are the setB, andfdescribes which hole each pig ...
Chapter 15 Cardinality Rules482 0020480135385502964448038 3171004832173501394113017 5763257331083479647409398 824733100004299531 ...
15.12. The Pigeonhole Principle 483 It turns out that it is hard to find different subsets with the same sum, which is why this ...
Chapter 15 Cardinality Rules484 The $500 Prize for Sets with Distinct Subset Sums How can we construct a set ofnpositive integer ...
15.13. A Magic Trick 485 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 ...
Chapter 15 Cardinality Rules486 For example, f 8 ~;K;Q;2};6}g (15.5) is an element ofX on the left. If the audience selects th ...
15.13. A Magic Trick 487 A 2 3 4 5 6 8 7 9 10 J Q K Figure 15.6 The 13 card ranks arranged in cyclic order. with 52 5 D2;598; ...
Chapter 15 Cardinality Rules488 All that remains is to communicate a number between 1 and 6. The Magician and Assistant agree ...
15.13. A Magic Trick 489 by the Subset Rule. On the other hand, we have jYjD 52 51 50 D132;600 by the Generalized Product Ru ...
Chapter 15 Cardinality Rules490 (b)There are 20 books arranged in a row on a shelf. Describe a bijection between ways of choosin ...
15.13. A Magic Trick 491 1 3 7 5 4 2 6 65622 tree code 1 2 3 4 5 432 Figure 15.7 Problem 15.5. LetXandYbe finite sets. (a)How ma ...
Chapter 15 Cardinality Rules492 Problems for Section 15.5 Practice Problems Problem 15.6. How many different ways are there to s ...
«
20
21
22
23
24
25
26
27
28
29
»
Free download pdf