The theory of generating functions is a simple and fun but powerful tool in enumerative combinatorics, which I will explain in the next few lectures. Digging into it, we shall see that it rests on some ideas from 'categorification': the more or less systematic replacement of sets by categories. One is 'groupoid cardinality': just as finite sets have cardinalities that are natural numbers, finite groupoids have cardinalities that are nonnegative rational numbers! Another is Joyal's theory of 'species'. A species is a type of structure that can be put on finite sets, of the sort we count in enumerative combinatorics.
In the rest of my lectures I'll continue talking about 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 fifth lecture of 2023. For other lectures go here:
math.ucr.edu/ho...
10 ноя 2023
