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 Dn, symmetric group Sn.
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.