**Instructor:** Nina Otter

(lastname AT math dot ucla dot edu)

**Class schedule:** MWF 4:00 - 4:50 pm, MS 5137

**Discussion:** Tu 4:00 - 4:50 pm, MS 5137

** Note:** There will be a revision lecture on Thursday 14 March at
5-6 pm in MS 5128

**Office Hours:** W 5-6 pm and F 3-3.50 pm MS 5626 or by appointment.

**Teaching Assistant:** David Soukup

(lastname AT math dot ucla dot edu)

**TA Office Hours:** Th 10-11am and F 5-6pm, MS 3921

**Textbook:** Miklos Bona, *Introduction to Enumerative and Analytic Combinatorics, Second Edition
* (MB), CRC Press, Second Edition

(see the CRC
page)

Additional reading will be posted on this page if necessary.

**Grading:** Homework: 10% + 10%, Midterm: 20%, Final: 60%.

**Difficulty:** This is an advanced undergraduate course in
Enumerative Combinatorics and its Application. The students are expected to
learn the theory and solve problems on the homeworks. The exams and especially
the homeworks will be challenging and require problem solving abilities.

Approximate course content by weeks:

- W1: Cardinality of a set, basic counting principles,
mathematical induction, counting permutations and injections
(Bona 1.1 - 1.4); lecture 1, lecture 2, lecture 3
- W2: Binomial coefficients, Pigeonhole principle, Multisets
(Bona 1.5 - 2.1);
lecture 4, lecture 5, lecture 6
- W3: Partitions, Stirling numbers of the second kind, counting surjections, inclusion-exclusion principle (Bona
2.2, 2.4); lecture 7, lecture 8
- W4: Ordinary and exponential generating functions (Bona 3.1 -
3.3); lecture 9, lecture 10, lecture 11
- W5: Eulerian numbers, the cycle structure of permutations (Bona
4.1, 4.2); lecture 12, lecture 13, lecture 14
- W6: Stirling numbers of the first kind, permutations of a
certain type (Bona 4.2); lecture 15, lecture 16. Additional reading (this will not be part
of the exam): On Solutions to a General Combinatorial Recurrence
- W7: Cycle structure and exponential generating functions (Bona
4.3); lecture 17
- W8: Graphs and isomorphisms, Cayley's formula (Bona 5.1);
lecture 18/19,
lecture 19/20
- W9: Rooted trees, Catalan numbers, generating functions of graphs (Bona 5.3 and
5.5); lecture 21, lecture 22, lecture 23, Stanley's
exercise
- W10: Hypergraphs with symmetries, finite projective planes,
error-correcting codes (Bona 8.1 - 8.3)

- exercise sheets (aka 'solve Nina's problems')
- 'solve your own problems' (SYOP) sheets

The exercise sheets will be posted here (on the course webpage) on Monday in week 2, 4, 6, 8, and will have to be handed in (in writing) on Tuesday of the following week at 4pm. These sheets will be graded and count towards 10% of the final grade.

About the SYOP sheets: A mathematics education will ideally enable you to build your mathematical skillset and pursue mathematical questions on an independent basis. For this I believe that it is crucial that you are given the opportunity to develop your own way of learning and doing mathematics. During the weeks 1, 3, 5, 7 you will therefore be asked to put in writing a discussion of some topic covered in the lecture, some additional topic that you might find interesting (but is still closely related to the lecture content), or a solution to an exercise of your choice (this does not need to be from the book, but needs to be related to the lecture content). For this assignment I would like you to pay particular attention to the quality of your (mathematical) writing. Of course, it goes without saying that mere transcription of parts of the book or other sources will not be accepted. Be creative!

You will have to hand in SYOP sheets on Tuesday at 4pm in week 2, 4, 6, 8. The SYOP sheets will be graded with a P/NP and count towards 10% of the final grade. All I ask you is to make a serious and honest attempt!

No late assignments will be accepted.

** Exercise sheets:**

- Exercise sheet 1
- Exercise sheet 2
- Exercise sheet 3
- Exercise sheet 4 ; for Problem 4 see Asymmetric graphs, by P. Erdös and A. Rényi

** Practice problems:**

**Final:** Thursday 21 March 2019, 11.30am - 2.30pm

*Last updated 10 Mar 2019*