Introduction to Combinatorics

Preface

Acknowledgments


1. Introductory Examples


1.1 A Simple Enumeration Problem


1.2 Regions of a Plane


1.3 Counting Labeled Trees


1.4 Chromatic Polynomials


1.5 Counting Hairs


1.6 Evaluating Polynomials


1.7 A Random Walk

Part I. Enumeration


2. Permutations and Combinations


2.1 Permutations


2.2 r-Arrangements


2.3 Combinations


2.4 The Binomial Theorem


2.5 The Binomial Coefficients


2.6 The Multinomial Theorem


2.7 Stirling's Formula


3. The Inclusion-Exclusion Principle


3.1 A Calculus of Sets


3.2 The Inclusion-Exclusion Principle


3.3 Some Applications of the Inclusion-Exclusion Principle


3.4 Derangements


4. Linear Equations with Unit Coefficients


4.1 Solutions Bounded Below


4.2 Solutions Bounded Above and Below


4.3 Combinations with Repetitions


5. Recurrence Relations


5.1 Recurrence Relations


5.2 Solution by Iteration


5.3 Difference Methods


5.4 A Fibonacci Sequence


5.5 A Summation Method


5.6 Chromatic Polynomials


6. Generating Functions


6.1 Some Simple Examples


6.2 The Solution of Difference Equations by Means of Generating Functions


6.3 Some Combinatorial Identities


6.4 Additional Examples


6.5 Derivatives and Differential Equations

Part II. Existence


7. Some Methods of Proof


7.1 Existence by Construction


7.2 The Method of Exhaustion


7.3 The Dirichlet Drawer Principle


7.4 The Method of Contradiction


8. Geometry of the Plane


8.1 Convex Sets


8.2 Tiling a Rectangle


8.3 Tessellations of the Plane


8.4 Some Equivalence Classes


9. Maps on a Sphere


9.1 Euler's Formula


9.2 Regular Maps in the Plane


9.3 Platonic Solids


10. Coloring Problems


10.1 The Four Color Problem


10.2 Coloring Graphs


10.3 More about Chromatic Polynomials


10.4 Chromatic Triangles


10.5 Sperner's Lemma


11. Finite Structures


11.1 Finite Fields


11.2 The Fano Plane


11.3 Coordinate Geometry


11.4 Projective Configurations

Part III. Applications


12. Probability


12.1 Combinatorial Probability


12.2 Ultimate Sets


13. Ramifications of the Binomial Theorem


13.1 Arithmetic Power Series


13.2 The Binomial Distribution


13.3 Distribution of Objects into Boxes


13.4 Stirling Numbers


13.5 Gaussian Binomial Coefficients


14. More Generating Functions and Difference Equations


14.1 The Partition of Integers


14.2 Triangulation of Convex Polygons


14.3 Random Walks


14.4 A Class of Difference Equations


15. Fibonacci Sequences


15.1 Representations of Fibonacci Sequences


15.2 Diagonal Sums of the Pascal Triangle


15.3 Sequences of Plus and Minus Signs


15.4 Counting Hares


15.5 Maximum or Minimum of a Unimodal Function


16. Arrangements


16.1 Systems of Distinct Representatives


16.2 Latin Squares


16.3 The Kirkman Schoolgirl Problem


16.4 Balanced Incomplete Block Designs


16.5 Difference Sets


16.6 Magic Squares


16.7 Room Squares

Answers to Selected Exercises

Index