## Introduction to Combinatorics

**Arizona State University**, **Fall 2021**

**Class meetings: Tuesdays and Thursdays 9–10:15am, WXLR A103**

Instructor: Zilin Jiang

Office hours: Tuesday and Thursday 2pm-3pm

Teaching assistant: Steven Alex Bradt

TA office hours: Wednesday 9am-10am and Friday 2pm-3pm

### Course description

Enumerating permutations and combinations of sets and multisets, inclusion-exclusion, recurrence relations, generating functions, Pólya theory and combinatorial structures.

**Prerequisites:** Students are assumed to have been introduced to elementary proof techniques and mathematical reasoning. These modest prerequisites are typically developed at the late sophomore or early junior level.

**Onboarding:**

- Please fill out the pre-semester questionnaire.
- (Optional) Learn how to use LaTeX (I recommend the tutorials on Overleaf).

**Asking questions:**

For class-related questions, it is best to come to office hours. Another possibility: Ask them on Slack. Administrative questions too can be asked there, especially if other students might be able to answer them or might learn from the answer.

### Grading

Homework 30% + Midterm 30% + Final 40% (+ Bonus 10%)

### Assignments

You are encouraged to type your submissions in LaTeX. All steps should be justified. You are strongly encouraged to do as much homework as possible individually; you will gain the most of out the course this way.

*Sources and collaboration policy.* Collaboration and use of external sources are permitted, but must be fully acknowledged and cited. Collaboration may involve only discussion; all the writing must be done individually. Failure to do so will be treated as cheating (see What is Academic Integrity?).

*Late policy and grade appeal policy. *In general no late homework will be accepted unless there is a genuine emergency backed up by official documents. No grade appeal will be considered after one week of the posting of the grade for any assignment.

There will be 7 assignments.

**Assignment 1** due on Aug 30.

**Assignment 2** due on Sep 13.

**Assignment 3** due on Sep 27.

**Assignment 4** due on Oct 18 (extended to Oct 20).

**Assignment 5** due on Nov 1.

**Assignment 6** due on Nov 15 (extended to Nov 16).

**Assignment 7** due on Nov 29.

### Exams

No make-up test will be given unless a student has notified the instructor before the test is given.

**Midterm:** Oct 7.

**Final:** Dec 9, 7:30–9:20am.

### Bonus

You will get up to 10% as a bonus for shooting a combinatorial video clip (2 to 5 minute long). Here is the timeline:

- Form a team of up to 5 people, and sign up for the bonus by Oct 14.
- Prepare a script and a storyboard, and get approved by Oct 28.
- Filming and post-production, and get feedback by Nov 16.
- Final presentation on Dec 2.

### Schedule

**Week 1**

Aug 19. The multiplication principle, counting tuples, factorial, falling factorial (*n*)* _{k}*.

**Week 2**

Aug 24. Birthday paradox, the complement principle, counting subsets, the bijection principle, the equivalence principle, the binomial coefficient *n* choose *k*.

Aug 26. Counting multisets, *m*-fold cover, counting circular arrangements, counting pairings.

**Week 3**

Aug 31. *Canceled*.

Sep 2. Combinatorial proofs, binomial coefficients, Pascal’s identity, Pascal’s triangle, Vandermonde’s identity.

**Week 4**

Sep 7. The binomial theorem, Stirling numbers of the second kind and their recurrence relation.

Sep 9. Counting surjective functions, partition numbers and their recurrence relation, the twelvefold way

**Week 5**

Sep 14. The inclusion-exclusion principle, counting primes, counting surjective functions.

Sep 16. Counting surjective functions (cont.), a formula for Stirling numbers of the second kind, the hat checker problem, derangement numbers.

**Week 6**

Sep 21. A formula and a recursive relation for derangement numbers, coefficients of a product of several polynomials.

Sep 23. Power series, generating functions, the generalized binomial theorem.

**Week 7**

Sep 28. Manufacturing generating functions, solving coefficients of a product of several generating functions.

Sep 30. A closed formula for the Fibonacci numbers, and another 2nd-order homogeneous linear recurrence.

**Week 8**

Oct 5. Theoretical and technical aspects of Visual Storytelling — Panel discussion for using video platform to communicate science

Oct 7. Midterm.

**Week 9**

Oct 12. *No class (fall break)*

Oct 14.* *Homogeneous linear recurrence, characteristic polynomials, recipe to solve a homogeneous linear recurrence.

**Week 10**

Oct 19. Tiling 2 x *n* rectangles with dominos, counting binary trees, the Catalan numbers.

Oct 21. Two applications of generating function in probability: the average number of times to roll a dice until a 6, the probability of ever reaching 0 for a frog at 1 that moves to the left by 1 or to the right by 2.

**Week 11**

Oct 26. The generating function and the recurrence of partition numbers, the pentagonal number theorem.

Oct 28. Franklin’s proof of the pentagonal number theorem, Ferrers diagrams. (Euler’s original proof)

**Week 12**

Nov 2. Coloring a square and a regular tetrahedron in two colors, permutation group, dihedral group *D _{n}*, symmetric group

*S*.

_{n}Nov 4. Group action, orbit, invariant, Burnside’s lemma, coloring a regular hexagon in *m *colors, Fermat’s little theorem.

**Week 13**

Nov 9. Cycle notation, the cycle index of a permutation group, the Polya enumeration theorem.

Nov 11. *No class (Veterans Day)*

**Week 14**

Nov 16. Weighted Burnside’s lemma, which implies Burnside’s lemma and the Polya enumeration theorem.

Nov 18. Proof of weighted Burnside’s lemma, the orbit-stabilizer theorem, the Stirling numbers of the 1st kind, and their recurrence.

**Week 15**

Nov 23. The five-card trick, the pigeonhole principle, Hall’s marriage theorem.

Nov 25. *No class (Thanksgiving Day)*

**Week 16**

Nov 30. Application of Hall’s marriage theorem to the five-card trick, and a proof of Hall’s marriage theorem.

Dec 2. Semester highlights and short film exhibition.