Skip to main content
1 of 4
Tom Copeland
  • 10.5k
  • 3
  • 57
  • 84

Exploring the algebra of multiplicative and compositional inversion (series inversion) for formal power series / ordinary generating functions (o.g.f.), I came across an infinite number of sets of involutive partition polynomials.

Given the o.g.f.,

$O^{(m)}(x) = x + c_1x^{m+1} + c_2 x^{2m+1} + c_3 x^{3m+1} + \cdots$

define the infinite set of reciprocal partition polynomials

$[R] = (1,R_1(u_1),R_2(u_1,u_2),R_3(u_1,u_2,u_3),...)$

as the expansion coefficients of the shifted reciprocal

$h(x) = \frac{x}{O^{(1)}(x)} = \frac{1}{1+c_1x +c_2 x^2 +\cdots} = 1 + R_1(c_1) x + R_2(c_1,c_2) x^2 + \cdots.$

The set of nonzero coefficients, the $m$-associahedra polynomials

$[A^{(m)}] = [1,A_1(u_1),A_2(u_1,u_2),...]$

of the expansion of the compositional inverse $(O^{(m)}(x))^{(-1)}$ of $O^{(m)}(x)$ are defined by

$(O^{(m)}(x))^{(-1)} = x + A_1(c_1)x^2 + A_2(c_1,c_2)x^3 + \cdots.$

The set of nonzero coefficients, the $m$-noncrossing-partitions polynomials

$[N^{(m)}] = [1,N_1(u_1),N_2(u_1,u_2),...]$

are the coefficients of the compositional inverse $(O^{(m)}(x))^{(-1)}$ in terms of the shifted reciprocals

$(O^{(m)}(x))^{(-1)} = x + A_1(c_1)x^2 + A_2(c_1,c_2)x^3 + \cdots$

$ = x + N_1(h_1)x^2 + N_2(h_1,h_2)x^3 + N_3(h_1,h_2,h_3) x^4 + \cdots$

$ = x + N_1(R_1(c_1))x^2 + N_2(R_1(c_1),R_2(c_1,c_2))x^3 + \cdots$;

that is, in the arbitrary, independent indeterminates $u_n$, $A_n(u_1,...,u_n)$ is given by the substitution of $R_k(u_1,...,u_k)$ for $u_k$ in $N_n(u_1,...,u_n)$, i.e.,

$A_n(u_1,u_2,...,u_n) = N_n(R_1(u_1),R_2(u_1,u_2),...,R_n(u_1,...,u_n)).$

Denote this substitution operation for the complete sets by

$$[A] = [N][R].$$

Then since $[A]^2 = [A][A]=[A][A]^{-1} = [A]^{0} = [I] = [R][R] = [R]^2$ with $[I]$ the substitution identity,

$$[A][R] = [N],$$

and the inverse noncrossing-partitions polynomials are given by

$$[N]^{-1} = [R][A].$$

Via an identity of Schur (circa 1947), it can be shown that the raising and lowering substitution operations

$$[A^{(m+1)}] = [A^{(m)}][N]^{-1} = [R][N]^{-m-1}$$

$$ = [N][A^{(m)}] = [N]^{m+1}[R]$$

are valid for $m = 0,\pm 1, \pm 2$, i.e., any integer, and, consequently, the $[A^{m}]$ are all involutions.

It also follows that

$$[A^{(m)}] = [N^{(m)}][R] = [N]^m[R]$$

and

$$[N] = [A^{(m+1)}][A^{(m)}].$$

Notes on special cases:

$[A^{(1)}]=[A]$ are the normalized re-indexed partition polynomials of A133437, the refined Euler characteristic polynomials of the associahedra, with linear coefficient unity, also related to dissections of convex polygons and various families of tree, among othe combinatorial constructs (cf. the MO-Q "Guises of the associahedra").

$[A^{(0)}] = [R]$ are the signed partition polynomials, refined Pascal polynomials, of signed OEIS A263633.

$[A^{(-1)}] = [R][N] = [K]$ are the special Schur self-convolution expansion coefficients / partition polynomials of A355201.

$ [A^{(-2)}] = [R][N]^2$ has a natural reduction to A286784, related to the Feynman diagrams of yet another quantum model for interacting fermions.

$[N^{(1)}]=[N]$ are the partition polynomials of A134264, enumerating the noncrossing partitions, a.k.a. the free moment partition polynomials generating the free cumulants, related also to Dyck lattice paths, trees, ... (cf. the MO-Q "Guises of the noncrossing partitions").

$[N^{(-1)}]=[N]^{-1}$ are the inverse noncrossing partition polynomials of A350499, a.k.a. the free cumulant partition polynomials generating the free moments from the free cumulants (cf. the MO-Q "Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory").

For $m \geq 1$, $[A^{(m)}]$ can be determined by the aeration-deaeration process

$A^{(m)}_n(u_1,u_2,...,u_n) = A_{mn}(0,0,...,u_1,0,0,...,u_2,0,0,...,u_n)$

with periodically placed swathes of $m-1$ zeros,

and, more surprisingly, so can $[N^{(m)}] = [N]^m$, i.e.,

$N^{(m)}_n(u_1,u_2,...,u_n) = N_{mn}(0,0,...,u_1,0,0,...,u_2,0,0,...,u_n).$

$[A^{(2)}]$ and $[N^{(2)}]$ (A338135) appear in the 1976 paper "Planar diagrams" by E. Brezin, Itzykson, Parisi, and Zuber with the indeterminates being connected Green functions in a quantum field model and in the recent arXiv paper "Connecting Scalar Amplitudes using The Positive Tropical Grassmannian" by Cachazo and Umbert. Even more refined partitions with the indeterminates being noncommutative are presented in "Noncommutative Symmetric Functions and Lagrange Inversion II: Noncrossing partitions and the Farahat-Higman algebra" by Novelli and Thibon, which reduce to these partition polynomials.

$[A^{(1)}] = [A]$ and $[A^{(2)}]$, for odd o.g.f.s, appear in a letter written by Isaac Newton in 1676 to Henry Oldenburg.

Tom Copeland
  • 10.5k
  • 3
  • 57
  • 84