## Table of Contents

**1. What is Combinatorics?**

1.1 Example: Perfect Covers of Chessboards

1.2 Example: Magic Squares

1.3 Example: The Four-Color Problem

1.4 Example: The Problem of the 36 Officers

1.5 Example: Shortest-Route Problem

1.6 Example: Mutually Overlapping Circles

1.7 Example: The Game of Nim

**2. The Pigeonhole Principle**

2.1 Pigeonhole Principle: Simple Form

2.2 Pigeonhole Principle: Strong Form

2.3 A Theorem of Ramsay

**3. Permutations and Combinations**

3.1 Four Basic Counting Principles

3.2 Permutations of Sets

3.3 Combinations of Sets

3.4 Permutations of Multisets

3.5 Combinations of Multisets

3.6 Finite Probability

**4. Generating Permutations and Combinations**

4.1 Generating Permutations

4.2 Inversions in Permutations

4.3 Generating Combinations

4.4 Generating r-Combinations

4.5 Partial Orders and Equivalence Relations

**5. The Binomial Coefficients**

5.1 Pascal's Formula

5.2 The Binomial Theorem

5.3 Unimodality of Binomial Coefficients

5.4 The Multinomial Theorem

5.5 Newton's Binomial Theorem

5.6 More on Partially Ordered Sets

**6. The Inclusion-Exclusion Principle and Applications**

6.1 The Inclusion-Exclusion Principle

6.2 Combinations with Repetition

6.3 Derangements

6.4 Permutations with Forbidden Positions

6.5 Another Forbidden Position Problem

6.6 Möbius Inversion

**7. Recurrence Relations and Generating Functions**

7.1 Some Number Sequences

7.2 Generating Functions

7.3 Exponential Generating Functions

7.4 Solving Linear Homogeneous Recurrence Relations

7.5 Nonhomogeneous Recurrence Relations

7.6 A Geometry Example

**8. Special Counting Sequences**

8.1 Catalan Numbers

8.2 Difference Sequences and Stirling Numbers

8.3 Partition Numbers

8.4 A Geometric Problem

8.5 Lattice Paths and Schröder Numbers

**9. Systems of Distinct Representatives**

9.1 General Problem Formulation

9.2 Existence of SDRs

9.3 Stable Marriages

**10. Combinatorial Designs**

10.1 Modular Arithmetic

10.2 Block Designs

10.3 Steiner Triple Systems

10.4 Latin Squares

**11. Introduction to Graph Theory**

11.1 Basic Properties

11.2 Eulerian Trails

11.3 Hamilton Paths and Cycles

11.4 Bipartite Multigraphs

11.5 Trees

11.6 The Shannon Switching Game

11.7 More on Trees

**12. More on Graph Theory**

12.1 Chromatic Number

12.2 Plane and Planar Graphs

12.3 A 5-color Theorem

12.4 Independence Number and Clique Number

12.5 Matching Number

12.6 Connectivity

**13. Digraphs and Networks**

13.1 Digraphs

13.2 Networks

13.3 Matching in Bipartite Graphs Revisited

**14. Pólya Counting**

14.1 Permutation and Symmetry Groups

14.2 Burnside's Theorem

14.3 Pólya's Counting formula