Return to Answer

Given the o.g.f.,

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

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

$(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)).$

$$[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

Via an identity of Schur (circa 1947), it can be shown that the raising operation

$[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.

Edit, Mar 3, 2023, due to a hasty transcription of notes--(too many pots on the burners). Superscripts added and a few exponents corrected, conforming to item 11 in the MO-Q "Guises of the noncrossing partitions":

(Start)

Explication of notation and implied identities:

For $m = 1,2,3,\cdots$, given the o.g.f.,

The $m$-associahedra polynomials

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

$(O^{(m)}(x))^{(-1)} = x + A^{(m)}_1(c_1)x^{m+1} + A^{(m)}_2(c_1,c_2)x^{2m+1} + \cdots.$

The $m$-noncrossing-partitions polynomials (name justified below)

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

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

$(O^{(m)}(x))^{(-1)} = x + A^{(m)}_1(c_1)x^{m+1} + A^{(m)}_2(c_1,c_2)x^{2m+1} + \cdots$

$ = x + N^{(m)}_1(h_1)x^{m+1} + N^{(m)}_2(h_1,h_2)x^{2m+1} + N^{(m)}_3(h_1,h_2,h_3) x^{3m+1} + \cdots$

$ = x + N^{(m)}_1(R_1(c_1))x^{m+1} + N^{(m)}_2(R_1(c_1),R_2(c_1,c_2))x^{2m+1} + \cdots$;

that is, in the arbitrary, independent indeterminates $u_n$, $A^{(m)}_n(u_1,...,u_n)$ is given by the substitution of $R_k(u_1,...,u_k)$ for $u_k$ in $N^{(m)}_n(u_1,...,u_n)$, i.e.,

$A^{(m)}_n(u_1,u_2,...,u_n) = N^{(m)}_n(R_1(u_1),R_2(u_1,u_2),...,R_n(u_1,...,u_n)).$

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

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

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

with the inverse substitutions given by

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

In particular, with the notational definitions $[A^{(1)}]=[A]$, $[N^{(1)}]=[N]$, and $[N^{(-m)}]=[N^{(m)}]^{-1}$, the inverse noncrossing-partitions polynomials are given by

New from notes:

If

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

then

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

If $[N][N] = [N]^{2} = [N^{(2)}]$, then the general relations are established, and this is true according to a theorem stated by Peter Bala in the OEIS. (My notes that I'm converting to a pdf contain a proof of this using the Schur identity mentioned below.) Therefore, the general results hinge on

$N_n(N_1(u_1),N_2(u_1,u_2),...,N_n(u_1,...,u_2))$

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

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

and the 'similarity' property

$R_n(u_1,u_2,...,u_n) = R_{2n}(0,u_1,0,u_2,...0,,u_n)$.

This equivalence in $[N]$ of self-substitution to 'aeration-deaeration' generalizes in a simple fashion as noted below.

(End)

Via an identity of Schur noted in the MO-Q "Guises of the noncrossing partitions", an extension of the Lagrange inversion formula, it can be shown that the raising operation

Historical note: The first few polynomials of $[A^{(1)}] = [A]$ for the inverse of the generic o.g.f. $O^{(1)}(x)$ and those for $[A^{(2)}]$, for odd o.g.f. $O^{(2)}(x)$ appear in a letter written by Isaac Newton in 1676 to Henry Oldenburg.

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.

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

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

Notes on special cases:

$[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").

Via an identity of Schur (circa 1947), it can be shown that the raising operation

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

and the lowering operation

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

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

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

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

Notes on special cases:

$[N^{(1)}]=[N]$ are the partition polynomials of A134264, enumerating the noncrossing partitions, a.k.a. the free cumulant partition polynomials generating the free moments from the free cumulants of free probability theory, 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 moment partition polynomials generating the free cumulants from the free moments of free probability theory (cf. the MO-Q "Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory").

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

$[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.

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

$[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.

With $u_1 = 1$ or $t$ and $u_k =0$ otherwise, the $[A^{(m)}]$ for $m \geq 1$ reduce to the Euler-Fuss-Catalan sequences of numbers (see, e.g., A001764).

With the above analysis, it can be proven that $N^{(3)}$ (A354622) naturally reduces to A173020; $N^{(2)}$ (A338135), to A120986 or A108767; $[N]$ (A134264) to A001263; $[N^{(-1)}] = [N]^{-1}$ (A350499), to A060693 or A088617; $[A^{(3)}]$, to A243663; $[A^{(2)}]$ (A359534) to A243662 or A102537; $[A^{(0)}]$ (signed A263633), to A007318; $[A^{(1)}]$ (normalized A133437 / A111785 ), to A033282 or A126216; $[A^{(-1)}]$ (A355201), to A001263; and $[A^{(-2)}]$, to A286784. These reductions are associated to numerous combinatorial constructs.

The reduction of the partition polynomials essentially involves reducing $[R]$ to the polynomials $(1\pm x)^n$ of the Pascal triangle A007318, showing that the identities $[A^{(m)}]= [N^{m}][R]$ are generalizations of a variant of the Dehn-Sommerville relations relating face polynomials, or f-polynomials $f(t)$, to h-polynomials $h(t)$ for, e.g., convex polytopes by $f(t) = h(1+t)$. E.g., the reduction of unsigned $[A]$ gives the face polynomials of the associahedra with that for the 3-D associahedron being $f_3(t) = 14+ 21t+9t^2+ 1 t^3$ with 14 vertices, 21 edges, 9 convex polygons (3 squares + 6 pentagons), and 1 associahedron, and the associated h-polynomial is $h_3(t) = f_3(t-1) = 1 + 6 t + 6 t^2 + t^3$, a Narayana polynomial, imposed by $[N] = [A][R]$, or, equivalently, $h_3(1+t) = f_3(t)$, imposed by $[N][R] = [A]$.