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