For this meeting, we will review binomial coefficients, then study inclusion/exclusion counting.
The most famous example of inclusion/exclusion is the “hat-check problem”, known more formally as the study of derangements.
The following Wikipedia articles give helpful summaries:
The hat-check problem has its own literature (Google for many more, and brace yourself for the sexist formulation):
Our books cover this material:
1 Let’s Count!, 2 Combinatorial Tools, and 3 Binomial Coefficients and Pascal’s Triangle (pp 1-57) covers this material in the most detail, at the most leisurely pace, of our various books.
Section 2 (pp 2-10) introduces binomial coefficients, through lattice paths. Section 4 (pp 32-40) introduces inclusion and exclusion, through derangements.
Chapter 1 What is Enumeration (pp 1-15) introduces both binomial coefficients and the inclusion-exclusion principle. This book reads as a very clear outline, with a spare style that leaves the reader to work out details.
This is intended as a text for graduate students, yet it is quite readable. One may prefer its mature style.
1.1 Elementary Counting Principles and 1.2 Subsets and Binomial Coefficients (pp 5-19) introduce binomial coefficients. 5.1 Inclusion–Exclusion (pp 179-191) introduces inclusion-exclusion.
Aigner includes many examples and exercises. We should consider these as examples to explore together in class.