Combinatorics

Week 1 | Week 2

Tuesday, January 12

Class notes

• Binomial coefficients
• Pascal’s triangle, recurrence relation
• Difference calculus, sum 1 to n
• Formulas for factorial, binomials (overcount and divide)
• “Bars and stars” counting
• Monomials of degree d in n variables

Wednesday, January 13

Office Hours

• Review of discrete calculus
• Sum of squares example
• Review of formula for binomial coefficients

Thursday, January 14

Class notes

• Binomial Theorem
• Monomials of degree 3 in 4 variables
• Bose-Einstein statistics
• Card shuffling example
• Walks on a grid
• Walks with a forbidden square

Suggested thinking

Take Thursday’s class a half hour further on your own: How do we deal with two or more forbidden squares? Figure this out by example, before looking in books. This is called inclusion-exclusion counting.

Suggested reading

I particularly recommend these expositions, from easy to advanced:

• 2015 Beeler - How to count
  • 1 Preliminaries
  • 2 Basic Counting
  • 3 The Binomial Coefficient
• 2011 Camina, Lewis - An introduction to enumeration
  • 1.1 Bijections,Permutations and Sequences
• 2007 Aigner - A Course in Enumeration
  • 1.1 Elementary Counting Principles
  • 1.2 Subsets and Binomial Coefficients

You may prefer these expositions:

• 1983 Pólya, Tarjan, Woods - Notes on Elementary Combinatorics
  • 1. Combinations and Permutations
• 2001 Martin - Counting: The art of enumerative combinatorics
  • Chapter 1. Elementary Enumeration
• 2003 Lovasz, Pelikan, Vesztergombi - Discrete mathematics
  • 1 Let’s Count!
• 2015 Petersen - Eulerian numbers
  • 1.1 Binomial coefficients
• 2016 Mariconda, Tonolo - Discrete calculus
  • 2.1 Sequences and Collections Having Distinct Elements

Along the way, try exercises that look interesting to you.