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/math.QA/0004133
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.uqam.ca/wp-conte...
Phillipe Flajolet and Robert Sedgewick, Analytic Combinatorics,
algo.inria.fr/flajolet/Publica...
Herbert S. Wilf, Generatingfunctionology, www.math.upenn.edu/~wilf/gfol...
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/home/baez/twf/
The cover picture here was adapted from one created by mathcircle and placed here:
commons.wikimedia.org/wiki/Fi...
23 ноя 2023
