Combinatorics

Week 2 | Week 3 | Week 4

Tuesday, January 26

Class notes

• Möbius Inversion
• Permutations with no adjacent pairs

Office Hours

• Zeta function and Möbius function as inverse matrices
• Poset interpretation of matrix inverse
• What to look at instead of Venn diagram when there are too many properties?

Thursday, January 28

Class notes

• Generating functions
• Monomials in two or three variables
• Making change using 1, 2, 5 cent coins
• A side trip (not on the exam!) into Algebraic Geometry

Suggested reading

• 2007 Aigner - A Course in Enumeration
  • 2.1 Algebra of Formal Series
  • 5.2 Möbius Inversion
• 1983 Pólya, Tarjan, Woods - Notes on Elementary Combinatorics
  • 3. Generating Functions
• 1994 Graham, Knuth, Patashnik - Concrete mathematics
  • 5.4 Generating Functions
• 2001 Martin - Counting: The art of enumerative combinatorics
  • Chapter 3. Generating Functions
• 2011 Camina, Lewis - An introduction to enumeration
  • 2.1 Counting – from Polynomials to Power Series
• 2015 Beeler - How to count
  • 5 Generating Functions
• 1994 Wilf - generatingfunctionology
  • Chapter 1: Introductory Ideas and Examples