Introduction to Combinatorics (eBook)

Front Cover 1
Introduction to Combinatorics 4
Copyright Page 5
Table of Contents 6
Preface 10
Acknowledgments 14
Chapter 1. Introductory Examples 16
1.1 A Simple Enumeration Problem 16
1.2 Regions of a Plane 23
1.3 Counting Labeled Trees 28
1.4 Chromatic Polynomials 32
1.5 Counting Hairs 37
1.6 Evaluating Polynomials 38
1.7 A Random Walk 42
Part I: ENUMERATION 46
Chapter 2. Permutations and Combinations 48
2.1 Permutations 50
2.2 r-Arrangements 53
2.3 Combinations 57
2.4 The Binomial Theorem 60
2.5 The Binomial Coefficients 63
2.6 The Multinomial Theorem 71
2.7 Stirling's Formula 73
Chapter 3. The Inclusion–Exclusion Principle 75
3.1 A Calculus of Sets 75
3.2 The Inclusion–Exclusion Principle 79
3.3 Some Applications of the Inclusion–Exclusion Principle 82
3.4 Derangements 85
Chapter 4. Linear Equations with Unit Coefficients 88
4.1 Solutions Bounded Below 88
4.2 Solutions Bounded Above and Below 93
4.3 Combinations with Repetitions 97
Chapter 5. Recurrence Relations 99
5.1 Recurrence Relations 99
5.2 Solution by Iteration 102
5.3 Difference Methods 105
5.4 A Fibonacci Sequence 109
5.5 A Summation Method 111
5.6 Chromatic Polynomials 111
Chapter 6. Generating Functions 124
6.1 Some Simple Examples 124
6.2 The Solution of Difference Equations by Means of Generating Functions 127
6.3 Some Combinatorial Identities 131
6.4 Additional Examples 133
6.5 Derivatives and Differential Equations 136
Part II: EXISTENCE 142
Chapter 7. Some Methods of Proof 144
7.1 Existence by Construction 144
7.2 The Method of Exhaustion 147
7.3 The Dirichlet Drawer Principle 151
7.4 The Method of Contradiction 153
Chapter 8. Geometry of the Plane 155
8.1 Convex Sets 155
8.2 Tiling a Rectangle 157
8.3 Tessellations of the Plane 162
8.4 Some Equivalence Classes 167
Chapter 9. Maps on a Sphere 170
9.1 Euler's Formula 171
9.2 Regular Maps in the Plane 176
9.3 Platonic Solids 178
Chapter 10. Coloring Problems 179
10.1 The Four Color Problem 179
10.2 Coloring Graphs 182
10.3 More about Chromatic Polynomials 183
10.4 Chromatic Triangles 189
10.5 Sperner's Lemma 190
Chapter 11. Finite Structures 195
11.1 Finite Fields 195
11.2 The Fano Plane 201
11.3 Coordinate Geometry 204
11.4 Projective Configurations 208
Part III: APPLICATIONS 212
Chapter 12. Probability 214
12.1 Combinatorial Probability 215
12.2 Ultimate Sets 219
Chapter 13. Ramifications of the Binomial Theorem 223
13.1 Arithmetic Power Series 223
13.2 The Binomial Distribution 227
13.3 Distribution of Objects into Boxes 229
13.4 Stirling Numbers 231
13.5 Gaussian Binomial Coefficients 233
Chapter 14. More Generating Functions and Difference Equations 241
14.1 The Partition of Integers 241
14.2 Triangulation of Convex Polygons 245
14.3 Random Walks 248
14.4 A Class of Difference Equations 254
Chapter 15. Fibonacci Sequences 257
15.1 Representations of Fibonacci Sequences 257
15.2 Diagonal Sums of the Pascal Triangle 260
15.3 Sequences of Plus and Minus Signs 261
15.4 Counting Hares 264
15.5 Maximum or Minimum of a Unimodal Function 265
Chapter 16. Arrangements 272
16.1 Systems of Distinct Representatives 273
16.2 Latin Squares 275
16.3 The Kirkman Schoolgirl Problem 278
16.4 Balanced Incomplete Block Designs 280
16.5 Difference Sets 283
16.6 Magic Squares 286
16.7 Room Squares 288
Answers to Selected Exercises 292
Index 308