Combinatorics, PWS, Boston, 1996

ISBN 0-534-95154-6. Available from Barnes & Noble and Amazon.com.

This text is a tool of sufficient flexibility to be useful in a wide variety of approaches to a third year course in combinatorics. Following a basic foundation in Chapters 1 & 2, the instructor is free to pi and choose the most appropriate topics from the remaining four chapters, each of which is independent of the other three.

The material in Chapter 3, Polya's Theory of Enumeration, is typically found closer to the end of comparable books, perhaps reflecting the notion that it is the last thing that should be taught in an undergraduate course. The author has endeavored both to make Polya's theory more accessible and make it possible for the topic to be addressed right after Chapter 2. It's placement in the middle of the book is intended to signal that it can be fitted in there, not that it must be.

Contents

1. The Mathematics of Choice

  • 1.1 The Fundamental Counting Principle
  • 1.2 Pascal's Triangle
  • 1.3 Elementary Probability (optional section)
  • 1.4 Binary Codes (optional section)
  • 1.5 Combinatorial Identities
  • 1.6 Four Ways to Choose
  • 1.7 The Binomial and Multinomial Theorems
  • 1.9 Newton's Identities

    • 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

    • 3. Polya'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 Polya's Theorem
  • 3.7 The Cycle Index Polynomial

    • 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

    • 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 Graphic Sequences

    • 6. Designs and Codes

  • 6.1 Latin Squares
  • 6.2 Balanced Incomplete Block Designs
  • 6.3 Linear Codes

    • The author welcomes contributions to the errata and will attempt to give appropriate recognition to the first person who brings a mistake to his attention, e.g., via E-mail to merris@csuhayward.edu