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

Classes:: Classes are over!
Office hours:: Tuesday 14:00--16:00, Thursday 13:00--14:00 in Korman Center #263. Also by appointment.
Blackboard:: Blackboard site for Math 222.
Instructor email:: darij.grinberg@drexel.edu
Mailbox:: Mathematics Common Room (Korman Center, 2nd floor).

Required:

Lecture notes that will be updated as the course progresses. (Source code on LMU servers and on GitLab.)

Recommended:

Fall 2018 Math 5705 at University of Minnesota, a similar class I taught a year ago and will mostly follow.
[Loehr]: Nicholas Loehr, Bijective Combinatorics, Chapman & 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 homework solutions): Fall 2018, Spring 2018, Fall 2017.

Remedial:

[LeLeMe]: 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.
[Newstead]: 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:

[Galvin]: David Galvin, Basic Discrete Mathematics: graduate-level introduction, built around the idea of generating functions.
[detnotes]: Darij Grinberg, Notes on the combinatorial fundamentals of algebra: detailed introduction to permutations and determinants; will be cited occasionally for some details we omit.

Week 1:

Material covered: Domino tilings, basic enumeration principles.
"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.
Homework set 1 (source code) with solutions (source code).

Week 2:

Material covered: Sums of powers, binomial coefficient basics.
Homework set 2 (source code) with solutions (source code).

Week 3:

Material covered: Counting basics.

Week 4:

Material covered: Counting basics, more binomial coefficients.
Midterm 1 (source code) with solutions (source code).

Week 5:

Material covered: Counting injections and surjections, Vandermonde convolution.
Homework set 3 (source code) with solutions (source code).

Week 6:

Material covered: More binomial coefficients, inclusion/exclusion.

Week 7:

Material covered: Compositions, multisets, the twelvefold way.
Midterm 2 (source code) with solutions (source code).

Week 8:

Material covered: The twelvefold way, partitions (introduction).
Homework set 4 (source code).

Week 9:

Material covered: Permutations.
Midterm 3 (source code) with solution sketches (source code).

Week 10:

Material covered: Permutations, odds and ends (only Monday).

Week 11:

Material covered: Generating functions, odds and ends.
Slides from the last class.

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 either handed in at the beginning of class, or submitted electronically (via Blackboard) in a format I can read (PDF, TeX or plain text if it works; no doc/docx!). If you submit a PDF, make sure that it is readable and does not go over the margins.
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.
Everything else is the same as for homework (yes, midterms are take-home), but collaboration is not allowed on midterms.

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.

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

Organization

Course description

Course materials

Course calendar

Grading and policies

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