Meetup summary

2025-06-06 - Unlabeled structures - integer partitions, regular languages, and necklaces

Recommended reading:

• Skim over/work through the examples in chapter I (unlabeled combinatorial structures; highlights only).
• 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 our 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.

Notes:

• Had a small, engaged group today. We got through essentially the entire agenda except for necklaces and Stirling S2-as-words.
• We struggled with some apparently-rudimentary operations to simplify the double-run combinatorial OGF to the form it had in the book (I.10). Our non-simplified OGF did appear to be equivalent and produced correct results, but it’s unclear if this has a material impact on the efficiency of coefficient extraction in practice. Would be an interesting exercise to pit these against each other for some large tests with FLINT.
• For completeness, here’s what we covered:
  • Brief pitch for using FLINT to do coefficient extraction.
  • Went over my example FLINT script which demonstrates how to implement the basic set of admissible constructions. Did not discuss the specific trade-offs and considerations in making computation efficient. (The reified form of OGFs actually matters for this.)
  • Integer partitions:
    • Definition and basic (unrestricted) OGF.
    • Restricted partitions, where the part sizes fall under some given set $T$. Introduced notation and OGFs.
    • Change-making problems. We touched on this before but restated it here expressly in the language of integer partitions.
    • Partitions with a fixed number of parts (not a direct restriction on part sizes). Correspondence with restricted part sizes via Ferrers diagram transpositions.
    • Partitions with distinct part sizes (basic powerset variation).
    • Partitions with odd-numbered sizes (restricted multiset construction).
    • By OGF manipulation, you find that the above counts are in correspondence! (Somewhat surprising/counterintuitive.)
    • Euler’s “computer scientist’s identity”. Count partitions using distinct-powers-of-two construction. Since this is equivalent to a base-2 number system, you also know that this is a simple geometric series. An interesting functional identity pops out.
  • Regular languages:
    • Definition: Start with a basic alphabet, $A$. Class of words is formed as $W = \operatorname{Seq}(A)$, sometimes denoted $A^*$. This implies that $a_n = |A|^n$, as expected clasically.
    • Alternate formulation of words by the “block” method (this is a special case for binary alphabets).
    • Using block form, computed OGF of longest run of as (e.g., assuming your alphabet is {a, b}).
    • S-regular languages, A-regular languages, and their equivalence.
    • Discussed an old Advent of Code problem which essentially involved the counting sequence of a regular language. IIRC, I solved this by simulating an NFA augmented with state multiplicity. This would be fun to solve by OGF instead (e.g., using FLINT).
    • OGF of words with exactly $k$ b instances. Agrees with classical result of $\binom{n}{k}$ for a string of length $n$.
    • Double-run statistics: instead of looking at longest runs of a, we’re now counting longest run of a or b. This is a more interesting problem (and is also the OGF we failed to simplify nicely).
  • Tip: When solving things analytically in practice, if you’re starting with a rational OGF, it’s often worth using partial fraction decomposition, simplifying/extracting coefficients on those simpler terms, and then recombining.