I am currently writing up a syllabus for a combinatorics course. I want to show the students that combinatorics is not just a collection of puzzles, but that it has connections to lots of interesting problems. Because the prerequisites for this course are fairly minimal (calculus and linear algebra), I think I’d do best to talk about applied uses. So, this is a request for cool applications of combinatorial techniques, which I can explain in a single lecture or less. Cool applications within math are also welcome, if they can be explained at a low level.
Details: The audience is mixed undergrad-grad. The undergrads will probably mostly be math majors, but I hope to haul in some engineers and computer scientists. I plan to organize the course into four main topics (which means none of them can be covered in depth):
- Generating functions and enumeration
- Graph theory
- Combinatorial geometry
Two things I am not doing: Symmetric functions and representation theory, because we’ll have a separate course on that, and asymptotics, because that would increase the prerequisites significantly.