Meetup summary

2025-11-07 - Labeled combinatorial structures - part 2

Recommended reading:

• Analytic Combinatorics chapter II (labeled combinatorial structures). If possible, try to read up to and through Theorem II.1 (admissible constructions for labeled classes).

Agenda:

• We’ll pick up where we left off last time, discussing the relabeling operations and connecting this to the partitional product and binomial convolution.
• Go over some basic combinatorial classes and set notation and operations.
• Work some small examples to get a feel for how EGFs work (urns, permutations, circular digraphs).
• Derive the “admissible constructions” for exponential generating functions (labeled structures). (This is Theorem II.1 in the book.)

Notes:

We started late, did a lot or review of OGFs and tangential material, and ended up getting through the “foundational” constructions (disjoint sum, labeled product) and special cases of permutations, urns, and cyclic graphs (sequence, set, and cycle). This laid the foundations for the basic framework of Theorem II.1, which we’ll cover next time (hopefully along with some worked examples).