Meetup summary

2025-02-28 - Worked problems with OGFs (unlabeled structures) - part 1

Recommended reading:

• Revisit Theorem I.1 from AC (admissible unlabeled constructions) if this is not fresh in your mind. We will be drawing on these constructions when working through examples
  • In general, it would be good to (re)read through chapters I.1—I.2 if you need a refresher on unlabeled structures and constructions.
• Chapters I.3—I.5 in AC, covering integer compositions/partitions, words/regular languages, and trees.

Agenda:

• Review the admissible constructions if needed (except for the cycle construction, which we have not yet derived).
• Integer compositions
  • Define (strict/weak) integer compositions.
  • Classical techniques
  • Using OGFs
  • Restricted compositions
• Integer partitions
  • Define integer partitions.
  • Not to be confused with set partitions! (As a preview: we’ll cover those later in the context of labeled structures.)
  • Classical techniques (using recurrences—not closed form!)
  • Using OGFs
  • Restricted compositions
  • Preview Hardy/Ramanujan asymptotics.
    • The Man Who Knew Infinity
• Words and regular languages.
  • Define both structures
  • Classical techniques
  • Using OGFs
  • Restricted words/languages. (This is where OGFs really excel.)
• For each worked example, the idea is to work through some examples “by hand” using clasical techniques, analytically with OGFs (without asymptotics), and then do some examples on the computer (if feasible). Possibly comparing both classical and lazy sequence coefficient extraction.

There is virtually 0 chance that we get through all of the above in one session. We’ll work through various problems based on peoples’ interest/familiarity.

Notes

We managed to cover the following at this session:

• Reviewed the definitions of combinatorial classes, the OGF interpretation, and fundamental constructions (neutral items, atoms, disjoint unions, and Cartesian products).
• Reviewed only the “core” constructions from Theorem I.1. Specifically:
  • Sequence construction. (This is heavily used in integer coding, e.g., in compositions and partitions.)
  • Powerset construction (combinatorial form only; no exp-log transformation.)
  • Multiset construction (combinatorial form only; no exp-log transformation.)
• Integer coding (for the positive integers specifically, as used when counting integer compositions and partitions): $\mathcal{I} = \operatorname{Seq}(\mathcal{Z})$.
• Notation for restricted classes, e.g., $\operatorname{Seq}_{\leq 3}(\mathcal{A})$ for sequences of length no greater than $3$, or $C^{\mathcal{T}} = \operatorname{Seq}(\operatorname{Seq}_{\mathcal{T}}(\mathcal{I}))$ for compositions restricted just to the class $\mathcal{T}$.
• Integer compositions:
  • Definition: Unique ways to sum to some integer $n$ where the parts must be positive integers (strict) and the order of parts matters.
  • Classical counting arguments to derive a result of $2^{n-1}$ for compositions of $n$.
  • Generating function (after simplification from foundational constructions): $$\frac{1 - z}{1 - 2z}$$
  • Manual coefficient extraction by symbolic methods
  • Coefficient extraction by computer.
  • Construction of restricted compositions (by part size).
  • Definition of $k$-compositions of $n$, both weak and strong.
  • Construction of $k$-compositions and generating function.
    • Coefficient extraction from this is pretty annoying, but we did one example by using the trick where you differentiate the geometric power series term-by-term, etc.
  • Classical technique to count $k$-compositions of $n$: stars and bars.
  • Analyzed restricted compositions of part sizes $\{1, 2\}$:
    • Generating function: $$C^{\mathcal{T}}(z) = \frac{1}{1 - z - z^2}$$
    • Recurrence implied by the above generating function.
    • The counting sequence is precisely the Fibonacci sequence. You can see this by comparison with the generating function or the recurrence.
  • Generalized Fibonacci numbers. In this case you restrict the part sizes to $\{1, 2, \dots, n\}$ for $n \ge 2$.

I’ve included some crossed out items above for topics that I had queued up but which we didn’t end up covering. I don’t plan to do those, but I do plan to cover partitions and regular languages in the future.