Combinatorics, 2nd Edition

Chapter 1: The Mathematics of Choice.

1.1. The Fundamental Counting Principle.

1.2. Pascal’s Triangle.

*1.3. Elementary Probability.

*1.4. Error-Correcting Codes.

1.5. Combinatorial Identities.

1.6. Four Ways to Choose.

1.7. The Binomial and Multinomial Theorems.

1.8. Partitions.

1.9. Elementary Symmetric Functions.

*1.10. Combinatorial Algorithms.

Chapter 2: The Combinatorics of Finite Functions.

2.1. Stirling Numbers of the Second Kind.

2.2. Bells, Balls, and Urns.

2.3. The Principle of Inclusion and Exclusion.

2.4. Disjoint Cycles.

2.5. Stirling Numbers of the First Kind.

Chapter 3: Pólya’s Theory of Enumeration.

3.1. Function Composition.

3.2. Permutation Groups.

3.3. Burnside’s Lemma.

3.4. Symmetry Groups.

3.5. Color Patterns.

3.6. Pólya’s Theorem.

3.7. The Cycle Index Polynomial.

Chapter 4: Generating Functions.

4.1. Difference Sequences.

4.2. Ordinary Generating Functions.

4.3. Applications of Generating Functions.

4.4. Exponential Generating Functions.

4.5. Recursive Techniques.

Chapter 5: Enumeration in Graphs.

5.1. The Pigeonhole Principle.

*5.2. Edge Colorings and Ramsey Theory.

5.3. Chromatic Polynomials.

*5.4. Planar Graphs.

5.5. Matching Polynomials.

5.6. Oriented Graphs.

5.7. Graphic Partitions.

Chapter 6: Codes and Designs.

6.1. Linear Codes.

6.2. Decoding Algorithms.

6.3. Latin Squares.

6.4. Balanced Incomplete Block Designs.

Appendix A1: Symmetric Polynomials.

Appendix A2: Sorting Algorithms.

Appendix A3: Matrix Theory.

Bibliography.

Hints and Answers to Selected Odd-Numbered Exercises.

Index of Notation.

Index.

Note: Asterisks indicate optional sections that can be omitted without loss of continuity.