Combinatorics

Week 1 | Week 2 | Week 3

Tuesday, January 19

Class notes

• Lattice walk with two holes
• Casting out nines to check arithmetic
• Inclusion-Exclusion with two properties A, B
• Hat check problem: Fixed point free permutations

Suggested exercise: How many integers 1..60 are not divisible by 2, 3, or 5?

Office Hours

• Arithmetic mod n
• Check lattice walk answer
• Suggested exercise solution

Wednesday, January 20

Office Hours

• 1..24 not divisible by 4 or 6
• 1..30 not divisible by 2, 3, or 5
• Crossing out fixed points in hat check problem

Thursday, January 21

Class notes

• Prime sieves
• Bayer filter
• 1..60 not divisible by 4, 5, or 6
• Euler’s totient function
• Product rule for m, n relatively prime
• Example (after class), m=5, n=12

Suggested reading

• 2007 Aigner - A Course in Enumeration
  • 5.1 Inclusion–Exclusion
• 1983 Pólya, Tarjan, Woods - Notes on Elementary Combinatorics
  • 4. Principle of Inclusion and Exclusion
• 2001 Martin - Counting: The art of enumerative combinatorics
  • Chapter 2. The Principle of Inclusion and Exclusion
• 2003 Lovasz, Pelikan, Vesztergombi - Discrete mathematics
  • 2.3 Inclusion-Exclusion
• 2011 Camina, Lewis - An introduction to enumeration
  • 1.3 The Principle of Inclusion and Exclusion
• 2015 Beeler - How to count
  • 7 Advanced Counting — Inclusion and Exclusion