This Week's Finds 17: counting derangements

A 'derangement' is a permutation where no element is mapped to itself: the cover picture lists the 24 permutations of the 4-element set {A,B,C,D}, and the 9 derangements are shown in blue. Here I show how to count derangements and find the generating function for derangements. A 'species' is a type of structure that can be put on finite sets: technically, it is a functor from the groupoid of finite sets and bijections to the category of sets. Any species has a 'generating function', which is a formal power series whose coefficients count how many ways we can put that structure on an n-element set for each n.
This is my penultimate lecture on combinatorics and categorification, loosely following this paper:
John Baez and James Dolan, From finite sets to Feynman diagrams, arxiv.org/abs/m...
And here's some more reading material - free books:
François Bergeron, Gilbert Labelle, and Pierre Leroux, Introduction to the Theory of Species of Structures, bergeron.math.u...
Phillipe Flajolet and Robert Sedgewick, Analytic Combinatorics,
algo.inria.fr/f...
Herbert S. Wilf, Generatingfunctionology, www.math.upenn...
This is one of a series of lectures at the University of Edinburgh on topics drawn from my column This Week's Finds. This is the 6th lecture of 2023. For other lectures go here:
math.ucr.edu/ho...
The cover picture here was adapted from one created by mathcircle and placed here:
commons.wikime...