Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

CHAP. 5] TECHNIQUES OF COUNTING 105 5.66. In a certain school, French (F), Spanish (S), and German (G) are the only foreign lang ...

106 TECHNIQUES OF COUNTING [CHAP. 5 Answers to Supplementary Problems 5.31. (a) 3 628 800; 39 916 800; 479 001 600; (b) log( 60 ...

CHAPTER 6 Advanced Counting Techniques, Recursion 6.1Introduction Here we consider more sophisticated counting techniques and pr ...

108 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6 Theorem 6.1: Suppose there areMkinds of objects. Then the number of combina ...

CHAP. 6] ADVANCED COUNTING TECHNIQUES, RECURSION 109 For example, s 1 ∑ i n(Ai), s 2 = ∑ i<j n(Ai∩Aj), s 3 = ∑ i 1 <i 2 &l ...

110 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6 (v) F 1 ∩F 2 ∩F 3 ∩F 4 has no element, that is, is empty. Hence|F 1 ∩F 2 ∩F ...

CHAP. 6] ADVANCED COUNTING TECHNIQUES, RECURSION 111 EXAMPLE 6.5 Consider six people, where any two of them are either friends o ...

112 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6 The following remarks about the above example are in order. (1) The equatio ...

CHAP. 6] ADVANCED COUNTING TECHNIQUES, RECURSION 113 6.7Linear Recurrence Relations with Constant Coefficients Arecurrence relat ...

114 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6 6.8 SOLVING SECOND-ORDER HOMOGENEOUS LINEAR RECURRENCE RELATIONS Consider a ...

CHAP. 6] ADVANCED COUNTING TECHNIQUES, RECURSION 115 EXAMPLE 6.11 Consider the celebrated Fibonacci sequence: an=an− 1 +an− 2 , ...

116 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6 EXAMPLE 6.12 Consider the following homogeneous recurrence relation: an= 6 ...

CHAP. 6] ADVANCED COUNTING TECHNIQUES, RECURSION 117 Remark 2: Ifris a root of multiplicitymof the characteristic polynomial
(x) ...

118 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6 SolvedProblems ADVANCED COUNTING TECHNIQUES, INCLUSION–EXCLUSION 6.1.A bage ...

CHAP. 6] ADVANCED COUNTING TECHNIQUES, RECURSION 119 6.6 Prove Theorem 6.5:Dn=n![ 1 − 11 !+ 21 !− 31 !+···+(− 1 )nn^1 !] Recall ...

120 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6 Fig. 6-2 RECURSION 6.11. Consider the second-order homogeneous recurrence r ...

CHAP. 6] ADVANCED COUNTING TECHNIQUES, RECURSION 121 SupplementaryProblems ADVANCED COUNTING TECHNIQUES, INCLUSION–EXCLUSION 6.1 ...

122 ADVANCED COUNTING TECHNIQUES, RECURSION [CHAP. 6 6.33. Find the unique solution to each recurrence relation with the given i ...

CHAPTER 7 Probability 7.1Introduction Probability theory is a mathematical modeling of the phenomenon of chance or randomness. I ...

124 PROBABILITY [CHAP. 7 EXAMPLE 7.1 (a) Experiment:Toss a coin three times and observe the sequence of heads(H )and tails(T )th ...