Department of Mathematical Sciences
Binghamton University

Syllabus of Math 386, Combinatorics

Fall 2009

Textbook

List of material covered

This list is subject to change and is not the same every year. The topics are not necessarily in order. We probably will not cover all the topics; (?) means we may or may not get to it.

• Chapter 1: What is Combinatorics?

  Introduction to combinatorics.
  Sections 1, 2, 4, 6 on various types of combinatorial problems.

• Chapter 2: Permutations and Combinations

  All sections: basic counting, with and without repetition. Application to probability.

• Chapter 4: Generating Permutations and Combinations

  Section 2: Inversions in permutations.

• Chapter 5: The Binomial Coefficients

  Sections 1-2, 4-5: Binomial identities, combinatorial proofs, binomial and multinomial theorems.
  Section 3: Unimodality and Sperner's theorem.

• Chapter 6: The Inclusion-Exclusion Principle and Applications

  Sections 1-5: The Principle of Inclusion and Exclusion and a variety of ways to apply it, notably combinations with repetition, derangements, permutations with forbidden positions, circular permutations with forbidden relations.

• Chapter 3: The Pigeonhole Principle

  Sections 1-2: The pigeonhole principle.

• Chapter 7: Recurrence Relations and Generating Functions

  Sections 1-3: Generating functions.
  Sections 4-5 (?): Recurrence relations.
  Section 6: Application to a geometry problem.

• Chapter 8 (?): Special Counting Sequences

  Section 1: Catalan numbers.
  Section 2: Stirling numbers.
  Section 4: Dividing the plane by lines.
  Section 5: Lattice paths and Schröder numbers.

• Chapter 10: Combinatorial Designs

  Section 1: Modular arithmetic.
  Section 4 (first half, to page 403): Latin squares.
  Extra: Affine planes (very brieflyl).