# Syllabus of Math 386, Combinatorics Fall, 2003

### Textbook

Introductory Combinatorics, 3rd edition, by Richard A. Brualdi.

### List of material covered

(This list is subject to change and is not the same every year.)

#### Chapter 1: What is Combinatorics?

Introduction to combinatorics.
Sections 1, 2, 3, 5, on various types of combinatorial problems.

#### Chapter 2: The Pigeonhole Principle

Sections 1-2: The pigeonhole principle.
Section 3: Ramsey's theorem.

#### Chapter 3: Permutations and Combinations

All sections: basic counting, with and without repetition.

#### Chapter 5: The Binomial Coefficients

Binomial identities, combinatorial proofs, binomial and multinomial theorems.
Unimodality and Sperner's theorem.
Section 6: Newton's binomial theorem.
(Section 7: omitted.)

#### Chapter 6: The Inclusion-Exclusion Principle and Applications

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 7: Recurrence Relations and Generating Functions

Recurrence relations: Section 7.1 and the beginning of 7.2.
Generating functions: Sections 7.4-6.

#### Chapter 8: Special Counting Sequences

Section 8.1: Catalan numbers.
Section 8.4: A Geometric Problem.