Applied Combinatorics With Problem Solving

Front Cover......Page 1
Back Cover......Page 2
Preface......Page 7
Contents......Page 11
1.1 Deduction......Page 15
1.2 Induction......Page 23
1.3 Sets and Relations......Page 36
1.4 Functions......Page 46
Review Problems......Page 53
2. Basic Counting Principles......Page 56
2.1 Sequential Counting......Page 57
2.2 Case-by-Case Counting......Page 64
2.3 Selections......Page 69
2.4 Selections with Unlimited Repetition......Page 78
2.5 Binomial Coefficients......Page 87
2.6 Permutations of Nondistinct Objects......Page 95
Review Problems......Page 99
3.1 The Union of Overlapping Sets......Page 102
3.2 Counting Restricted Arrangements......Page 110
3.3 Distributions......Page 116
Review Problems......Page 123
4.1 Algorithms......Page 125
4.2 Asymptotic Analysis of Algorithms......Page 133
4.3 Enumerating Permutations and Combinations (Optional)......Page 138
Review Problems......Page 145
5.1 Graph Models......Page 148
5.2 Paths and Connectedness......Page 159
5.3 Circuits and Cycles......Page 164
5.4 Planar Graphs......Page 173
5.5 Graph Colorings......Page 178
Review Problems......Page 185
6.1 Breadth First Search......Page 187
6.2 Trees......Page 194
6.3 Tree Algorithms......Page 202
Review Problems......Page 212
7.1 Generating Function Models......Page 214
7.2 Calculating Coefficients......Page 221
7.3 Partitions......Page 227
7.4 Exponential Generating Functions......Page 233
Review Problems......Page 238
8.1 Recurrence Relation Models......Page 240
8.2 Homogeneous Linear Recurrences......Page 248
8.3 Nonhomogeneous Linear Recurrence Relations......Page 256
Review Problems......Page 264
9.1 Symmetry Groups and Burnside\'s Theorem......Page 267
9.2 The Cycle Index......Page 275
Review Problems......Page 282
10.1 Directed Graphs......Page 284
10.2 Networks......Page 292
10.3 Network Flows......Page 300
Hints and Answers to Odd-Numbered Problems......Page 313
Index......Page 331