Enumerators for Permutations: Examples & Exponential Generating Functions

Sterling numbers of first kind count permutations by cycle structure, while Sterling numbers of second kind count set partitions. Both have exponential generating functions: for second kind, ∑ S(n,k) n! t^n = (e^t - 1)^k/k!; for first kind, ∑ s(n,k) n! t^n = log(1+t)^k/k!. These functions reveal deep connections between permutation cycles and set partitions, with their matrices being inverses.

This comprehensive section covers Stirling numbers of both kinds and their combinatorial interpretations. The lecture discusses the limitations of the characteristic equation method, explaining that it works when the characteristic equation has k distinct real roots, but fails when roots are repeated or complex. For repeated roots, the solution form changes to include terms like α₀λⁿ + α₁nλⁿ + ... + αₘ₋₁nᵐ⁻¹λⁿ for a root λ with multiplicity m. For complex roots, the solution includes conjugate pairs that can be rewritten using trigonometric functions. The lecture then introduces Stirling numbers of the first kind, denoted s(n,k) or [n k], as coefficients in the expansion of the falling factorial x⁽ⁿ⁾ = x(x-1)(x-2)...(x-n+1) = Σs(n,k)xᵏ. The lecture derives the recurrence relation s(n+1,k) = s(n,k-1) - n·s(n,k) from the identity x⁽ⁿ⁺¹⁾ = x⁽ⁿ⁾(x-n). The section shows how to arrange Stirling numbers in a triangular array similar to Pascal's triangle, with the recurrence allowing computation of each entry from previous entries. The lecture establishes that the absolute value |s(n,k)| counts the number of permutations of n elements with exactly k cycles. The section introduces cycle notation for permutations, showing how to decompose permutations into disjoint cycles by following the mapping from each element until returning to the starting element. The lecture then introduces Stirling numbers of the second kind, denoted S(n,k) or {n k}, as counting the number of ways to partition a set of n elements into k non-empty, unlabeled subsets. The lecture derives the recurrence relation S(n+1,k) = k·S(n,k) + S(n,k-1) by considering where the (n+1)th element goes: either it forms a new subset (contributing S(n,k-1) ways) or it joins one of the k existing subsets (contributing k·S(n,k) ways). The section establishes that S(n,k) counts the number of ways to partition a set of n elements into k non-empty, unlabeled subsets, and that the number of surjective functions from an n-element set to a k-element set is k!·S(n,k).

Stirling numbers of first kind [n,k] count the number of ways to seat n people around k identical circular tables with no empty tables, while Stirling numbers of second kind S(n,k) count the number of ways to partition a set of n labeled objects into k non-empty unlabeled subsets. The two types are related through matrix inversion, where the matrices of first and second kind are inverses of each other. Stirling numbers of first kind can be computed using the falling factorial expansion (x)_n = Σ s(n,k) x^k, while Stirling numbers of second kind use the formula S(n,k) = (1/k!) Σ (-1)^(k-i) C(k,i) i^n. Both types have reference relations: s(n,k) = -s(n-1,k-1) + (n-1)s(n-1,k) for first kind, and S(n,k) = S(n-1,k-1) + kS(n-1,k) for second kind.

The unsigned Stirling numbers of the first kind, denoted as [n k], can be defined combinatorially as the number of permutations of n elements with exactly k cycles, or algebraically through the generating function ∑[n k]x^k = x(x+1)(x+2)...(x+n-1). These definitions are proven equivalent by showing they satisfy the same recurrence relation [n+1 k] = [n k-1] + n[n k] with identical initial conditions, and additionally, it is shown that [n+1 2] = n!H_n, where H_n is the nth harmonic number.

Stirling numbers emerge from specific specializations of orthogonal polynomial theory. When B_k = k+1 and λ_k = k, mixed moments μ(n,k) equal Stirling numbers of the first kind s(n,k), which count permutations of n elements with exactly k cycles. The coefficient side ν(n,k) equals Stirling numbers of the second kind S(n,k), which count set partitions of n elements into k blocks. The generating function for Stirling numbers of the second kind is ∑_{k=0}^n S(n,k) x^k = x(x-1)(x-2)...(x-n+1), while for the first kind it involves alternating signs: ∑_{k=0}^n s(n,k) x^k = x(x+1)(x+2)...(x+n-1). These numbers appear throughout combinatorics, algebra, and analysis.

Analytic combinatorics studies generating functions as complex functions to derive asymptotic formulas for combinatorial coefficients. The transfer theorem states that if a generating function F(z) has a dominant singularity at z=ρ with local behavior (ρ - z)^(-α), then the coefficient f_n ~ C × n^(-α-1) × ρ^(-n). For many combinatorial classes, this yields asymptotic behavior of the form f_n ~ C × n^(-3/2) × ρ^(-n), showing universal square-root singularities.

Analytic combinatorics applies complex analysis to extract asymptotic information from generating functions. Two principles govern this approach: singularity locations determine exponential growth rates (e.g., 1/(1-2z) at z=1/2 yields 2^n growth), while singularity types determine sub-exponential corrections. Rational functions yield polynomial corrections; algebraic functions yield power-law corrections; differential equations yield more complex asymptotics. This framework enables automatic asymptotic analysis for many generating function classes. Applications span biology (biomembrane shapes), computer science (queueing theory), and physics (quiver gauge theories), demonstrating how pure mathematics techniques solve concrete combinatorial problems across disciplines.

This lecture demonstrates how the symbolic method combined with meromorphic asymptotics provides immediate asymptotic estimates for combinatorial coefficients. The key principle is that the dominant singularity closest to the origin determines all asymptotic growth behavior. Examples include: (1) Derangements (permutations with no fixed points) with generating function e^(-z)/(1-z), yielding n!/e; (2) Surjections (coupon collector sequences) with generating function 1/(2-e^z), yielding (log 2)^n/(2 log 2); (3) Double surjections requiring each element to appear at least twice; (4) Alignments (sequences of labeled cycles) with generating function 1/(1-log(1/(1-z))); (5) Set partitions (Bell numbers) with generating function (1/(1-z))^r/r!, yielding r^n/(r! * r). The method works even for complex generating functions, with error terms exponentially small.

Analytic combinatorics derives asymptotic results directly from combinatorial constructions. The core procedure involves: (1) finding the smallest real pole of the generating function, (2) calculating the residue by evaluating the numerator at the pole and dividing by the derivative of the denominator, (3) the coefficient asymptotics are residue/alpha times beta^n where beta = 1/alpha. This method works for rational and meromorphic generating functions arising from combinatorial specifications.

Analytic combinatorics uses the symbolic method to define combinatorial constructions and derive generating functions that enumerate combinatorial classes; once generating functions are obtained, recurrence relations can be computed to analyze quantities of interest, with applications including determining bit requirements for encoding structures and estimating growth rates of combinatorial sequences like partition numbers.

Eulerian polynomials encode permutation statistics: descent number counts positions where σ(i) > σ(i+1), exceedance number counts where σ(i) > i, and major index sums descent positions. These statistics are equidistributed with inversions, yielding the q-analog of n!. Eulerian polynomials are palindromic and unimodal. A q-analog replaces t with qt, preserving these properties. The exponential generating function ∑ₙ aₙ(q)tⁿ/n! = (1-t)⁻¹ ∑ₙ xⁿ/(qⁿ-1) generalizes Euler's formula. This framework connects permutation enumeration to symmetric function theory and provides tools for studying combinatorial structures through algebraic methods.

Eulerian numbers A(n, k) count the number of permutations of n elements with exactly k-1 descents, where a descent is a position i such that w(i) > w(i+1). These numbers satisfy the recurrence A(n, k) = k × A(n-1, k) + (n-k+1) × A(n-1, k-1), and their generating function is given by the Eulerian polynomial a_n(x) = ∑_{m=0}^∞ m^n × x^m / (1-x)^{n+1}, which can be further unified into the two-variable generating function ∑_{n=0}^∞ a_n(x) × t^n / n! = (1-x) × e^{(1-x)t} / (1-x).

This section develops the theory of Eulerian polynomials, which encode descent statistics of permutations. The descent number of a permutation is the number of indices where σ(i) > σ(i+1). The Eulerian polynomial A_n(t) is the generating function for descent numbers, with coefficients counting permutations with exactly k descents. These polynomials are symmetric and have real roots. Refined Eulerian polynomials condition on the first element of the permutation, and these refined polynomials are interlacing (roots alternate between polynomials). For type B (hyperoctahedral group), similar descent statistics and Eulerian polynomials can be defined, with analogous interlacing properties.

Bivariate generating functions extend the symbolic method by using two variables: z marks the size of combinatorial objects, while u marks the value of a parameter (such as number of cycles, leaves, or zero bits). The coefficient of z^n u^k in the ordinary bivariate generating function gives the number of objects of size n with parameter value k. The symbolic method's transfer theorems (union, Cartesian product, sequence) apply directly to these bivariate generating functions, allowing systematic derivation of generating function equations from combinatorial specifications. This approach enables computation of not just average values but the full distribution of combinatorial parameters, including moments, standard deviations, and extremal values.

Hypersimplices are polytopes from intersecting the unit cube with Σx_i = k. They are coordinate-permutation invariant. Eulerian polynomials A_r(y) count permutations of [r] with i descents. For r=3, A_3(y) = 1 + 4y + y^2. These polynomials are palindromic and their coefficients equal volumes of hypersimplices. Mixed Eulerian polynomials generalize Eulerian polynomials using mixed volumes of hypersimplices. For sequence a_1,...,a_k with Σa_i=n, the polynomial packages mixed Eulerian numbers in generating function form. When k=1 and a_1=n, it reduces to the ordinary Eulerian polynomial. These polynomials provide a systematic way to study mixed Eulerian numbers, which were previously studied individually.