Darij Grinberg: Enumerative Combinatorics (Math 222), Fall 2022

Classes:: Classes are over!
Notes:: 2019 notes (will be completed as the course progresses).
Blackboard:: https://learn.dcollege.net/ultra/courses/_325805_1/cl/outline.
Gradescope:: https://www.gradescope.com/courses/443845.
Piazza:: https://piazza.com/drexel/fall2022/math222.
Instructor email:: darij.grinberg@drexel.edu

All weeks:

ZIP archive containing all the lecture notes and assignments listed below.

Week 1:

Lecture 1 (source code): administrativa; domino tilings introduction.
Lecture 2 (source code): counting domino tilings; basic enumeration principles.
Lecture 3 (source code): Fibonacci numbers; symmetric domino tilings.
"Homework set 0" with solutions (source code). This contains three sample exercises with fairly detailed solutions (more detailed than you need to write). The source code contains instructions on the use of LaTeX.

Week 2:

Lecture 4 (source code): introduction to finite sums and products.
Lecture 5 (source code): introduction to finite sums and products; factorials; binomial coefficients.
Lecture 6 (source code): basic properties of binomial coefficients.
Homework set 1 (source code) .

Week 3:

Lecture 7 (source code): further properties of binomial coefficients.
Lecture 8 (source code): further properties of binomial coefficients; counting subsets.
Lecture 9 (source code): counting lacunar subsets.
Homework set 2 (source code) .

Week 4:

Lecture 10 (source code): more subset counting; mappings.
Lecture 11 (source code): counting mappings; interchange of summations.
Homework set 3 (source code) .

Week 5:

Lecture 12 (source code): interchange of summations; counting permutations (the beginning); isomorphism principle.
Lecture 13 (source code): counting permutations (the end); telescope principle; sign-reversing involutions.
Lecture 14 (source code): double counting; the polynomial identity trick.
Midterm 1 (source code) .

Week 6:

Lecture 15 (source code): the Chu--Vandermonde identity.
Lecture 16 (source code): counting maps.
Lecture 17 (source code): counting surjective maps; sums of powers.

Week 7:

Lecture 18 (source code): bijective proofs and double counting.
Lecture 19 (source code): the principle of inclusion and exclusion.
Lecture 20 (source code): applications of inclusion and exclusion.
Homework set 4 (source code).

Week 8:

Lecture 21 (source code): compositions and weak compositions.
Lecture 22 (source code): multisubsets, multinomial coefficients.
Lecture 23 (source code): the twelvefold way (introduction).
Announcement of Math T480: Elementary Number Theory (Spring 2023).

Week 9:

Midterm 2 (source code) .
Lecture 24 (source code): equivalence classes, the twelvefold way (U to L).
Lecture 25 (source code): the twelvefold way (L to U and U to U), partitions.
Lecture 26 (source code): permutations (introduction).

Week 10:

Lecture 27 (source code): permutations (cycle decomposition).
Homework set 5 (source code).

Week 11:

Lecture 28 (source code): permutations (more cycles, inversions, lengths, signs, descents, Eulerian numbers).
Lecture 29 (source code): lattice paths, Catalan numbers, generalizations.
Lecture 30 (source code): generating functions (preview).
Midterm 3 (source code).

No Copyright:

The above lecture notes and assignments have been released under the CC0 license, i.e., are dedicated to the public domain. They can be copied, modified and distributed without permission. See the license for details.

Grading matrix:

40%: homework sets (the lowest score will be dropped if all homework sets are submitted).
20%: midterm 1.
20%: midterm 2.
20%: midterm 3.

There will be no final exam.

Grade scale:

These numbers are tentative and subject to change:

A: (80%, 100%].
B: (60%, 80%].
C: (40%, 60%].
D: [0%, 40%].

Homework policy:

Collaboration and reading is allowed, but you have to write solutions in your own words and acknowledge all sources that you used.
Asking outsiders (anyone apart from Math 222 students and Drexel staff) for help with the problems is not allowed. (In particular, you cannot post homework as questions on math.stackexchange before the due date!)
Late homework will not be accepted. (But keep in mind that the lowest homework score will be dropped.)
Solutions have to be submitted via Gradescope (see above for the link). Don't forget to assign pages to the problems you solve!
This is a proof-based class. All claims have to be proven, unless they were proven in class or are sufficiently elementary to be taken for granted at this level (e.g., uniqueness of prime factorization). Even if the problem asks "find X satisfying A", you will have to prove that your X indeed satisfies A. Solutions will be graded based on both correctness and readability.

Midterm policy:

Late midterms will not be accepted unless agreed in advance and with serious justification.
Collaboration is not allowed on midterms.
Everything else is the same as for homework (yes, midterms are take-home).

Expected outcomes:

Students will understand and be able to reason about the staples of enumerative combinatorics such as binomial coefficients, permutations, and partitions. Students will have some familiarity with bijective, inductive and algebraic proofs of combinatorial identities, and will have seen various approaches to solving enumeration problems.

Required:

The 2019 notes, which will be updated as the course progresses. (Source code on LMU servers and on GitLab.) Keep in mind that they (1) only cover roughly 70% of our material, and (2) contain details and tangents that we will skip in class.

Recommended:

[Loehr11]: Nicholas Loehr, Bijective Combinatorics, Chapman and Hall/CRC 2011: comprehensive and high-quality textbook, goes much further into the subject than we will.
A list of undergraduate-level texts and notes on enumerative combinatorics (including many freely accessible ones). Warning: various difficulties and levels of sophistication.
Previous courses with similar content: Fall 2019, Fall 2018, Spring 2018, Fall 2017. Include homework sets, often with solutions -- might be worth the occasional read.

Remedial:

[LeLeMe16]: Eric Lehman, F. Thomson Leighton, Albert R. Meyer, Mathematics for Computer Science, 2018: a great introduction to rigorous mathematics. Chapters 1--5 cover the Math 220 basics we will need: proofs, sets, relations, in/sur/bijections. Later chapters go into topics, even covering a bit of what we will do in this course.
[Newste19]: Clive Newstead, An Infinite Descent into Pure Mathematics: introduction to proofs and mathematical thinking. (Work in progress.)
Richard Hammack, Book of Proof: introduction to proofs.
A list of undergraduate-level texts and notes on proofs (freely accessible).

Further:

[Galvin17]: David Galvin, Basic Discrete Mathematics: graduate-level introduction, built around the idea of generating functions.
[Grinbe21]: Darij Grinberg, An Introduction to Algebraic Combinatorics: a follow-up course at the graduate level.
[Grinbe15]: Darij Grinberg, Notes on the combinatorial fundamentals of algebra: detailed introduction to permutations and determinants; will be cited occasionally for some details we omit.

Math 222: Enumerative Combinatorics, Fall 2022
Professor: Darij Grinberg

Organization

Course description

Course calendar

Grading and policies

Sources

Math 222: Enumerative Combinatorics, Fall 2022 Professor: Darij Grinberg