Syllabus of Math 386, Combinatorics
Textbook
Introductory Combinatorics, 3rd edition, by Richard A. Brualdi.
List of material to be covered
This list is not absolutely fixed. The material mentioned in Chapters
1, 2, 3, 5, 6, and 10 generally forms the heart of the course but it is
supplemented and may be partially replaced by other material.
Chapter 1: What is Combinatorics?
Introduction to combinatorics.
Sections 1-3, 5, possibly 7, on various types of combinatorial problems.
Chapter 2: The Pigeonhole Principle
Sections 1-2: The pigeonhole principle.
Chapter 3: Permutations and Combinations
All sections: basic counting, with and without repetition.
Chapter 4: Generating Permutations and Combinations
Part or all may be covered.
Chapter 5: The Binomial Coefficients
Binomial identities, combinatorial proofs, binomial and multinomial theorems.
Possibly omitted: Section 6: Newton's binomial theorem.
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, permutations with forbidden
positions, circular permutations with forbidden relations.
Derangements.
Chapter 10: Combinatorial Designs
Orthogonal sets of Latin squares (Section 4).
Modular arithmetic (with some finite field arithmetic) and applications
to orthogonal Latin squares (Sections 1, 4).
Partially Ordered Sets and Equivalence Relations
(Optional.) This is in Sections 4.5 and 5.7.
Recurrence Relations and Generating Functions
(Optional.)
Recurrence relations: Sections 7.1-3.
Generating functions: Sections 7.4-7 and 8.1.
Other optional topics
(not necessarily listed here) may be covered at the discretion of the instructor.