Meetup summary

2025-03-14 - Worked problems with OGFs (unlabeled structures) - part 2

Recommended reading:

• Prerequisites for classical counting techniques
• Chapters I.3—I.4 in AC, covering integer compositions/partitions and words/regular languages.

Agenda:

• Happy $\pi$ day! Eat some pizza pie and fruit pie.
• Watch Neil’s meandering river simulation and speculate as to how $\pi$ pops out (or decide that it’s all just a modeling farce).
• Detour into fundamental counting structures—classical style. These will appear later in AC (or have already appeared many times) and are widely useful, both in counting and probability, but also elsewhere. For each, the plan is to define the number, derive a recurrence relation, derive a closed form (where possible) using classical techniques, and to briefly discuss applications or useful identities.
  • Rising and falling factorials.
  • Binomial coefficients. Pretty well known, but so important that it’s worth digging into.
  • Stirling numbers of the first kind (“cycle numbers”). I also plan to share a cool bijection that I came up with to prove the rising factorial sum identity (change of basis from powers to rising factorials—write-up to follow). This identity is widely known, but I couldn’t find any satsifactory explanations online or in textbooks that made a convincing, clear, and self-contained combinatorial argument.
    • The Foata transformation: connecting LTR maxima and cycles in random permutations.
  • Stirling numbers of the second kind (“partition numbers”), along with the change of basis identity (from falling factorials to powers).
  • Lah numbers (unofficially “Stirling numbers of the third kind”). This is mostly just for completeness to close the loop on the change of basis trifecta. I’m still working on a combinatorial derivation of the identities and have yet to actually come across these coefficients in the wild.
• 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.

As last time, we will not get through all of the above, but will instead drill into the areas that people are intersted in.

Notes:

As expected, we didn’t get through the agenda—we didn’t even get to OGFs.

Here’s what we did do:

• Derived an expression for the probability that two “random” integers $p$ and $q$ are coprime. (It’s not actually a well-defined probability distribution because you can’t have a uniform distribution over all of $\mathbb{N}$, but there’s probably some sense in which you could spell it as a limit.)
  • Showed that this probability comes to (in the “limit”) $\frac{1}{\sum_{n=1}^{\infty} \frac{1}{n^2}}$. The denominator is the infamous Basel problem.
  • Geometric “proof” of the value of the denominator above: $\frac{\pi^2}{6}$. We didn’t quite get through the whole thing due to time.
  • Happy $\pi$ day!
• Ate some pizza pi(e).
• Briefly went over some combinatorial prerequisites, most notably PIE and the subset/partitioning interpretation of binomial coefficients.
• Binomial coefficients.
  • Derived the well-known binomial sum for $(a+b)^n$ for non-negative integers $n$ (i.e., not the general binomial theorem). Noted this can always be rewritten as $c(x + 1)^n$ for some $c$ and $x$ as long as both $a$ and $b$ are non-zero. This is the form most often seen (and which will come up often in recursive combinatorial arguments).
  • Derived the main recurrence relation (as used when building Pascal’s triangle).
  • Hinted at what the general OGF might look like (but didn’t drill into it this time). Note that for fixed $n$, you can do this with a univariate OGF. To cover all $n$ and $k$, you need to parameterize with another variable.
• Permutation prerequisites
  • Definition
  • Three equivalent notations: two-line, one-line, and cycle notation. Noted that two-line notation is ambiguous and is best avoided, since it can be used to denote forward or inverse permutations.
• Stirling numbers of the first kind (cycle numbers).
  • Defined as the number of partitions of $n$ distinct objects into exactly $k$ (disjoint) cycles.
  • Derived the fundamental recurrence for S1 numbers (including base cases).
  • Discussed the special case of $\begin{bmatrix} n \\ 1 \end{bmatrix}$.
• Stirling numbers of the second kind (partition numbers).
  • Defined as the number of ways to partition $n$ distinct objects into exactly $k$ subsets where the subsets themselves are unlabeled.
  • Derived the fundamental recurrence for S2 numbers (including base cases).
  • Discussed the special case of $\begin{Bmatrix} n \\ 1 \end{Bmatrix}$.
  • Discussed the special case of $\begin{Bmatrix} n \\ n - 1 \end{Bmatrix}$.
• Lah numbers (“Stirling numbers of the third kind”).
  • Defined as the number of ways to partition $n$ distinct objects into exactly $k$ ordered tuples where the tuples themselves are unlabeled.
  • Derived the fundamental recurrence for Lah numbers (including base cases).
• Noted that the three Stirling-type numbers look very similar in their recurrences except for the coefficient of the recursive case for $(n-1, k)$. Moreover, they can all be seen as counting distinct ways to partition a set of $n$ objects into $k$ parts with different requirements on the parts themselves (sets, sets with a cyclic order, fully-ordered lists).
• The above “definitions” are not necessarily the ones used universally and were not necessarily how they were even originally developed (particularly in the case of Lah numbers), though I assume S2 numbers were introduced this way. Instead, we focused on combinatorial definitions since these are more easily motivated by our use cases. I plan to sprinkle in some worked problems and explanations as to where and how these arise in the wild. (This point was not discussed, but adding for clarity.) We did not get to the change-of-basis identities, but these further solidify the interrelation between the three Stirling-type numbers.
• Argued that S2 is more “fundamental” than S1 numbers and their definitions should be swapped in an ideal world. This is further supported by the fact that $$\begin{Bmatrix} n \\ k \end{Bmatrix} \le \begin{bmatrix} n \\ k \end{bmatrix} \le \left\lfloor \begin{matrix} n \\ k \end{matrix} \right\rfloor .$$ Sadly, the cat’s already out of the bag. 🤷