# 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. |