The Art and Craft of Problem Solving

204 CHAPTER 6 COMBINATORICS corresponds to (5,0, 6). This method uniquely encodes each triple with a string of 1 3 symbols conta ...

6.2 PARTITIONS AND BIJECTIONS 205 We can compute the exact number. Each sorority is uniquely determined by its collection of 10 ...

206 CHAPTER 6 COMBINATORICS integer? For example, 4=1+3=3+1=2+2=1+1+2 = 1 +2+ 1 = 2+ 1 + 1= 1 + I + 1 + I, so when n = 4, there ...

6.3 THE PRINCIPLE OF INCLUSION-EXCLUSION 207 6.2.32 In Example 6.2.4 on page 200, the incorrect argument overcounted by 48. Acco ...

208 CHAPTER 6 COMBINATORICS systematic way to handle these situations. In simplest fonn, PIE states that the number of elements ...

6.3 THE PRINCIPLE OF INCLUSION-EXCLUSION 209 Visualize each set as a rubber disk. The cardinality of the union of the sets corre ...

210 CHAPTER 6 COMBINATORICS will be G) intersections of pairs of these sets, and for each of them, we will count x once. Hence S ...

choose from, so 6.3 THE PRINCIPLE OF INCLUSION-EXCLUSION 211 IDnHI = C5^6 ). By similar reasoning, ID n H n SI = ei). Notice tha ...

212 CHAPTER 6 COMBINATORICS bi is sitting to the left of gi or vice versa. For each case, there will be 7! possibili­ ties, sinc ...

6.3 THE PRINCIPLE OF INCLUSION-EXCLUSION 213 Let us apply these simple concepts to get a new proof of the complement form of PIE ...

214 CHAPTER 6 COMBINATORICS is equal to the alternating sum 1 -(a + b + ... ) -(ab + ac + ... ) + .... • Problems and Exercises ...

6.4 RECURRENCE 215 insight by focusing on the "local" situation, the transition from n = 1 to n = 2, and then, more generally, t ...

216 CHAPTER 6 COMBINATORICS These values are precisely those of the Fibonacci numbers (see Problem l.3 .l8 on page 10 ). Recall ...

Thus, in particular, if we define In:= �(a n W), 6.4 RECURRENCE 217 then In + I = In + In -I. Since this also satisfies the bo ...

218 CHAPTER 6 COMBINATORICS which you can check by carefully drawing all the possibilities. Before we rest, let's look at the 7- ...

6.4 RECURRENCE 219 Solution: Define the generating function f( x) =CO+CIX+C 2 X^2 + .... Squaring, we have f(x)^2 = CoCo + (CICO ...

220 CHAPTER 6 COMBINATORICS Thus we can conclude that en = _ 1 (2n). n+ 1 n For a fascinating, purely combinatorial derivati ...

Stirling Numbers Problems 6.4.16-- 6.4.22 develop a curious "dual" to the Binomial Theorem. 6.4. 16 For n, k positive integers w ...

Chapter 7 Number Theory Number theory, the study of the integers Z, is one of the oldest branches of mathe­ matics, and is a par ...

7.1 PRIMES AND DIVISIBILITY 223 There are infinitely many primes. This was Problem 2.3.2 1 on page 51, but in case you did not s ...