Meetup summary

2025-03-28 - Stirling numbers

Recommended reading:

• Prerequisites for classical counting techniques
• Optionally take a look at the FLINT docs. I plan to go over the core stuff of interest though.

Agenda:

• Review all three “Stirling-style numbers” (S1, S2, and Lah (“S3”)). Definitions, recurrences, and closed forms where possible.
• Derive the core polynomial change-of basis identities in all pairwise directions.
  • Convert any identity involving a rising factorial factor into one involving a falling factorial (or vice versa) using rising/falling factorial manipulations. This also motivates the signed Stirling number conventions. (I don’t like the signed variants as much because the fundamental combinatorial interpretations of Stirling numbers all involve the unsigned forms.)
• Efficient extraction of high coefficients using the FLINT library (we’ll probably use the python-flint wrapper as it’s much more practical for exploration).
  • Part of the efficiency comes from the built-in FLINT numerical techniques, but OGF representation still matters a lot for performance. We’ll go over some pathological examples and show how to rewrite them to make them faster.
  • Rule of thumb: wherever possible, simplify the GF symbolically and define the whole thing in-line. Avoid delaying/abstracting functions and in particular avoid composing power series.

Notes:

• We went through the Stirling reviews and derivations but did not get to FLINT or computational methods.
• Derived the following identity by a (discrete) function counting argument (all functions and summing over the disjoint sets of functions using surjections over size-$k$ subsets): $$x^n = \sum_{k=0}^n \begin{Bmatrix} n \\ k \end{Bmatrix} x^{\underline{k}}$$
• Derived the following identity by forming a bijection between the expansion of the rising factorial into a sum of products and $k$-cycles of $n$ objects. This one was not super well received; I’ll probably revisit it later and post a write-up on this site. I could not find any good textbook or online treatments of this identity, so I came up with my own bijection for the proof involving nonstandard notation. $$x^{\overline{n}} = \sum_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} x^{k}$$
• Derived the following identity by counting the ways to distribute $$ distinct items into $$ distinct bins with linear order of the items in each bin in two separate ways. This was probably the best received identity argument because it leans on a direct “concrete” counting argument, while the others require more abstraction. $$x^{\overline{n}} = \sum_{k=0}^n \left\lfloor \begin{matrix} n \\ k \end{matrix} \right \rfloor x^{\underline{k}}$$