Mathematics for Computer Science
14.11. References 613 In total, how many work days will Iavoidin the coming year? Problem 14.49. Twenty people work at CantorCor ...
Chapter 14 Cardinality Rules614 is called acword. A password can be a cword which does not contain any of the subwords “fails”, ...
14.11. References 615 Now to start proving (14.15), letMSbe themembershipfunction for any setS: MS.x/D ( 1 ifx 2 S; 0 ifx...S: L ...
Chapter 14 Cardinality Rules616 (f)Finally, explain why (14.21) immediately implies the usual form of the Inclusion- Exclusion P ...
14.11. References 617 (g)Asngoes to infinity, the number of derangements approaches a constant frac- tion of all permutations. W ...
Chapter 14 Cardinality Rules618 Exam Problems Problem 14.55. (a)Letrbe the number of lengthnbinary strings in which 011 occurs s ...
14.11. References 619 Problem 14.57. A robot on a point in the 3-D integer lattice can move a unit distance in one positive dire ...
Chapter 14 Cardinality Rules620 (e)LetHSFbe the set of all straight flush hands; that is, the hand is both a straight and a flus ...
14.11. References 621 is it? X r 1 Cr 2 Cr 3 Cr 4 Dn; ri 2 N n r 1 ; r 2 ; r 3 ; r 4 ! D‹ (14.25) Hint:How many terms are there ...
Chapter 14 Cardinality Rules622 Problem 14.64. When an integerkoccurs as thekth element of a sequence, we’ll say it is “in place ...
14.11. References 623 Hint:LetMbbe the number of menus where, if Doritos appear at all, they only appear atbreakfast; likewise, ...
Chapter 14 Cardinality Rules624 Problem 14.68. According to the Multinomial Theorem 14.6.5,.x 1 Cx 2 C Cxk/ncan be expressed ...
14.11. References 625 Exam Problems Problem 14.70. Each day, an MIT student selects a breakfast from amongbpossibilities, lunch ...
...
15 Generating Functions Generating Functions are one of the most surprising and useful inventions in Dis- crete Mathematics. Rou ...
Chapter 15 Generating Functions628 We’ll use typical generating function reasoning to derive a simple formula for G.x/. The appr ...
15.2. Counting with Generating Functions 629 15.2 Counting with Generating Functions Generating functions are particularly usefu ...
Chapter 15 Generating Functions630 donuts, and by (15.6) we have B.x/D 1 .1x/^2 : So how many ways are there to select a mix ofn ...
15.2. Counting with Generating Functions 631 xnin the productA.x/B.x/is the sum of all the coefficients of the terms on this di ...
Chapter 15 Generating Functions632 15.2.4 Counting Donuts with the Convolution Rule We can use the Convolution Rule to derive in ...
«
27
28
29
30
31
32
33
34
35
36
»
Free download pdf