Math 184: General Course Outline

Catalog Description

184. Enumerative Combinatorics. (Formerly numbered 180.) Lecture, three hours; discussion, one hour. Requisites: courses 31A, 31B, 61 and 115A. Permutations and combinations, counting principles, recurrence relations and generating functions. Application to asymptotic and probabilistic enumeration. Ideal for students in mathematics and physics. P/NP or letter grading.

Textbook

M. Bona, Introduction to Enumerative Combinatorics , 2nd Ed., Chapman and Hall/CRC

Outline update: Pak, I., 12/15

Schedule of Lectures

Lecture Section Topics

1

1.1 - 1.3

Basic counting methods (induction, pigeonhole principle).

2

1.4 - 2.2

Binomial coefficients, multinomial coefficients, set partitions, Stirling numbers.

3

2.3 - 2.4

Integer partitions, partitions into odd and distinct numbers. Euler's Pentagonal theorem.

4

3.1 - 3.4

Ordinary and exponential generating functions.

5

4.1 - 4.3

Permutations, Number of cycles and descents. Derangements via Inclusion-Exclusion Principle.

6

4.4 - 4.5

Inversions. Counting permutation by a cycle type.

7

5.1 - 5.2

Counting labeled trees. Different proofs of Cayley's formula.

8

5.3

Catalan numbers. Plane and binary trees.

9

5.4 - 5.5

Chromatic polynomial. Enumerations of connected graphs and Eulerian graphs.

10

9.1 - 9.2

Sequences. Unimodality. Log-concavity.