Meetup summary

2025-05-23 - Unlabeled structures - integer partitions, regular languages, and necklaces

Recommended reading:

• Skim over/work through the examples in chapter I (unlabeled combinatorial structures).
• Optionally take a look at the FLINT docs. I plan to go over the core stuff of interest though.
• Read over some sample programs for computer-aided coefficient extraction:
  • OGFs with Flint
  • Integer partition counting (special case of the above) by classical techniques:
    • Dynamic programming with a 2D memo table. The general idea is to compute $k$-partitions of $n$ with dynamic programming and then compute all partitions of $n$ by summing over $k$. This is relatively quick but requires $O(n^2)$ memory.
    • Dynamic programming with a 1D memo table using Euler’s pentagonal number theorem. This is the fastest technique of those covered here to compute exact partition numbers, but it also requires the most specialized knowledge. Conversely, the OGF technique is slow but very general and quick to write with no specialized understanding of partition structures in general.

Agenda:

• With the cycle construction under old belt now, we have all the tools to work through the following examples (which we haven’t yet covered):
  • Integer partitions (including special cases/restricted partitions, coin change counting, etc.)
  • Regular languages/finite automata. (There’s an isomorphism between the two.) Regular languages are particularly interesting because you can spell many restricted sequence counting problems as counting restricted word classes under a regular language. We’ll also include a preview of Stirling partition (S2) numbers via this lens (they’re normally treated as labeled structures using exponential generating functions).
  • Counting necklaces. Define what a necklace is and then work an example or two via OGFs. We’ll also compare/contrast this with bracelets, which we can’t enumerate with the cycle construction as derived (due to some extra symmetries).
• “Real world” coefficient extraction with FLINT. I plan to demo computer-aided coefficient extraction for the worked examples which are not feasible to do by hand. There are also some rules of thumb you’ll want to keep in mind when using this approach in practice since some (equivalent) formulations of formal power series are less computationally efficient than others.