# Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory

In the background sections below, I establish the relations among characterizations of the action of Virasoro / Kac–Schwarz operators of 2D gravity models presented in terms of Laurent series by Alexandrov (see also the Kharchev ref in his paper) and basic partition polynomials associated with free probability theory (and, therefore, random matrices and quantum field theory).

For those already familiar with free probability theory, my question is

What are some combinatorial/diagrammatic models for the free moment partition polynomials, giving the free cumulants in terms of the free moments?

Related partition and reduced polynomials have trees, lattice paths, convex polyhedra, and other diagrammatics as well as Grassmannians, positroids, Coxeter groups, and Lie derivatives plastered all over them. There is even an association with monstrous moonshine via the compositional inversion of Laurent series with the free cumulant partition polynomials as numerators (cf. "Modular Matrix Models" by He and Jejjala). Ebrahimi-Fard et al., in a recent paper noted below, do give a diagrammatic formulation for both the free moment and free cumulant partition polynomials in terms of noncrossing partitions.

Background, details, and potentially useful associations:

Classical formal moments and cumulants:

Bereft of any notions of probability, the formal classical moments $$\hat{m}_n$$ and cumulants $$\hat{c}_n$$ are related via an inverse pair of functions—the exponential and the logarithm—as (in umbral notation with, e.g., $$\langle(\hat{c}_\bullet)^n\rangle=\hat{c}_n$$)

$$\ln[\langle e^{\hat{m}_\bullet x}\rangle] = \langle e^{\hat{c}_\bullet x}\rangle,$$

the partition polynomials of A127671 give the cumulants in terms of the moments whereas those of A036040 give the moments in terms of the cumulants. Both have have numerous interpretations in diagrammatics and enumerative combinatorics with diverse applications in pure analysis and mathematical physics.

Free formal moments and cumulants:

Again stripped of any notions of probability, an equivalent algebraic relation can be developed for the free moments $$m_n$$ and free cumulants $$c_n$$ of free probability theory. The Voiculescu polynomials / free cumulant partition polynomials of A134264 generate the free moments from the free cumulants, which can be determined by finding the inverse (i.e., compositional inverse) of a formal power series in terms of the coefficients of its shifted reciprocal (i.e., shifted multiplicative inverse).

More precisely, given a formal power series, or ordinary generating (o.g.f.), with vanishing constant,

$$O(x)=x+a_1 x^2 +a_2 x^3 +a_3x^4 + \dotsb,$$

the associated formal free cumulants are defined by

$$C(x) = \frac{x}{O(x)} = \frac{1}{1+a_1 x +a_2 x^2 +a_3x^3 + \cdots} = 1+c_1 x +c_2 x^2 +c_3x^3 + \dotsb,$$

and the o.g.f. of the formal free moments is defined by

\begin{align*} M(x) = O^{(-1)}(x) ={} &x+m_1 x^2 +m_2 x^3 +m_3x^4 + \dotsb \\ ={} &(\frac{x}{C(x)})^{(-1)}= (\frac{x}{1+c_1 x +c_2 x^2 +c_3x^3 + \dotsb})^{(-1)} \\ ={} & x + c_1 \; x^2 + ( c_2 + c_1^2) \; x^3 + (c_3 + 3\; c_2c_1 + c_1^3) \;x^4 \\ &\quad+\; ( c_4 + 2\;c_2^2 + 4\; c_3\; c_1+6 \;c_2 \;c_1^2+c_1^4 ) \; x^5 + \cdots. \end{align*}

Conversely,

\begin{align*} C(x) = \frac{x}{O(x)} ={} & 1+c_1 x +c_2 x^2 +c_3x^3 + \dotsb \\ = \frac{x}{M^{(-1)}(x)} ={} & \frac{x}{(x+m_1 x^2 +m_2 x^3 +m_3x^4 + \dotsb)^{(-1)}} \\ ={} & [1-m_1x +(2m_1^2-m_2)x^2+(-5m_1^3+5m_1m_2- m_3)x^3+( 14 m_1^4 - 21 m_1^2 m_2 + 6 m_1 m_3 + 3 m_2^2 - m_4)x^4+\dotsb]^{-1} \\ ={} & 1 + m_1x +(-m_1^2+m_2)x^2+ (2m_1^3 -3m_2m_1+m_3)x^3 + (-5m_1^4+10m_2m_1^2-4m_3m_1-2m_2^2+m_4)x^4+(14 m_1^5 - 35 m_1^3 m_2 + 15 m_1^2 m_3 + 15 m_1 m_2^2 - 5 m_1 m_4 - 5 m_2 m_3 + m_5)) x^5 +\dotsb \end{align*}

in which the inverse of $$M(x)$$ is expressed in terms of the re-normalized partition polynomials of A133437 (a.k.a. A111785) for the formal compositional inversion of a formal power series, the refined Euler characteristic partition polynomials (or signed refined face partition polynomials) of the associahedra.

As an aside, the partition polynomials of A263633 for multiplicative inversion of a power series can then be used for spot checks by hand:

from the OEIS entry

$$\frac{1}{1+b_1x +b_2x^2+b_3x^4+\cdots} = 1-b_1x +(b_1^2-b2)x^2 + (-b_1^3 + 2b_1b_2-b_3)x^3+ \dotsb,$$

so

$$c_3 =-(-m_1)^3 + 2(-m_1)(2m_1^2-m_2)-(-5m_1^3+5m_1m_2-m_3)= 2m_1^3 -3m_1m_2+m_3.$$

Compilation of formulas with related OEIS entries, containing associated combinatorics:

The first few moments in terms of the cumulants are given by the cumulant partition polynomials of A134264 and A125181, which enumerate noncrossing partitions (NCP), marked Dyck paths, certain sets of trees, etc., $$\DeclareMathOperator\NCP{NCP}$$ \begin{align*} & m_1 = c_1 = \NCP_1(1,c_1), \\ & m_2 = c_2 + c_1^2 = \NCP_2(1,c_1,c_2), \\ & m_3 =c_3 + 3\; c_1 \; c_2 + c_1^3 = \NCP_3(1,c_1,c_2,c_3), \\ & m_4 = c_4 + 4\; c_1 \; c_3+2\;c_2^2+6\;c_1^2 \;c_2+c_1^4 = \NCP_4(1,c_1,c_2,c_3,c_4), \end{align*}

with the reduced polynomials obtained by setting $$c_n=t$$,

\begin{align*} & m_1^r(t) = t, \\ & m_2^r(t) = t + t^2, \\ & m_3^r(t) =t + 3\; t^2 + t^3 , \\ & m_4^r(t) = t + 6t^2+6\;t^3+t^4, \end{align*}

the Narayana polynomials of A001263 and A090181, whose coefficients sum to the Catalan numbers A000108,

The converse relations are

\begin{align*} & c_1= m_1 \\ & c_2 =-m_1^2+m_2 \\ & c_3 = 2m_1^3 -3m_2m_1+m_3 \\ & c_4 =-5m_1^4+10m_2m_1^2-4m_3m_1-2m_2^2+m_4 \\ & c_5 = 14 m_1^5 - 35 m_1^3 m_2 + 15 m_1^2 m_3 + 15 m_1 m_2^2 - 5 m_1 m_4 - 5 m_2 m_3 + m_5 \end{align*}

(not in the OEIS, but soon as A350499). These polynomials up to $$c_4$$ can be found on p. 26 of "Operads of (noncrossing) partitions, interacting bialgebras, and moment-cumulant relations" by Ebrahimi-Fard, Foissy, Kock, and Patras; Ex. 37 of Terry Tao's notes on free probability; and p. 22 of "Enumerative geometry, tau-functions and Heisenberg–Virasoro algebra" by Alexandrov (although he doesn't mention the relation to the free moments and cumulants nor even free probability in general, he draws connections to Virasoro/Witt group actions).

There is a derivational analogy between the classic moment partition polynomials (CMPs) and those of the free moments (FMPs). The partial derivative of each CMP (A127671) with respect to the distinguished first indeterminate ($$x$$ in the Lang table) is proportional to a refined Euler characteristic partition polynomial of the permutohedras (A133314) whereas the analogous derivatives of the FMPs are proportional to the refined Euler characteristic partition polynomials of the associahedra, e.g.,

$$\frac{\partial c_4}{\partial {m_1}} = 4 \; ( -5m_1^3+5m_2m_1^2-m_3),$$

in terms of the o.g.f.s,

$$\partial_{m_1} \; C(x) = x \; \partial_x \; x \; M^{(-1)}(x)$$

(missing factor of $$x$$ added June 11, 2023).

In addition, both the free and classic cumulant partition polynomials are Appell Sheffer polynomials in the distinguished indeterminate $$c_1$$; i.e., $$\partial_{c_1} P_n = n \; P_{n-1}$$, e.g.,

$$\frac{\partial m_4}{\partial c_1} = 4 \; m_3,$$

so

$$\partial_{c_1} \; (M(x)/x) = x \; \partial_x \; x \; (M(x)/x),$$

or

$$\partial_{c_1} \; M(x) = x^2 \; \partial_x \; M(x),$$

interweaving $$sl_2$$, binomial transforms, and Laguerre polynomials into the tapestry.

(End)

The reduced polynomials obtained by setting $$m_n = -t$$ and removing the subsequent overall sign,

\begin{align*} & c_1^r(t)= t \\ & c_2^r(t) =t^2+t \\ & c_3^r(t) = 2t^3 + 3t^2+t \\ & c_4^r(t) =5t4+10t^3+6t^2+t \\ & c_5^r(t) = 14 t^5 + 35 t^4 + 30 t^3 + 10t^2 + t, \end{align*}

these coefficients are those of A088617 and A060693 with the big Schroeder numbers A006318 as the row sums, as I show below.

The sequence of coefficients of the highest order term in each moment partition polynomial is the Catalan sequence A000108, which can easily be proved by setting $$m_1=1$$ and all other moments to zero and noting that $$x/(x+x^2)^{(-1)}$$ gives an o.g.f for the Catalan sequence (consistent with the semi-circular law in free probability theory and random matrices).

The row sums of the unsigned moment partition polynomials are

\begin{align*} & 1 \\ & 1 \\ & 1+1=2 \\ & 2+3+1=6 \\ & 5+10+4+2+1=22 \\ & 14+35+15+15+5+5+1 =90, \end{align*}

giving the initial terms of the sequence of sums as $$1,2,6,22,90$$, which are the initial terms of A006318, the big Schroeder numbers.

The associated reduced polynomials:

To obtain the reduced moment partition polynomials and verify the associations noted above, set $$m_n = -t$$, and then from the o.g.f.s of A088617 and A086810, the shifted reverse face polynomials of the associahedra (cf. also A033282 and A126216 for relation to dissections of polygons and Schroeder/Dyck lattice paths), it can be established that

\begin{align*} C(x;t) ={} & \frac{x}{O(x;t)}=\frac{x}{M^{(-1)}(x;t)} \\ ={} & \frac{1}{1+tx +(2t^2+t)x^2+(5t^3+5t^2+ t)x^3+( 14 t^4 + 21 t^3 + 9 t^2 + t)x^4+\cdots}, \\ ={} & 1 -[\; tx +(t^2+t)x^2+ (2t^3 +3t^2+t)x^3 + (5t^4+10t^3+6t^2+t)x^4+(14 t^5 + 35 t^4 + 30 t^3 +10t^2 + t) x^5 +\cdots \;] \\ ={} & \frac{1+x+\sqrt{1-2(2t+1)x+x^2}}{2} . \end{align*}

So, combinatorial models described in A088617 and A060693 for the coefficients of the reduced polynomials, and in linked arrays, such as A055151, suggest refined models for the full partition polynomial, e.g., Schroeder paths and trees, as well as connections to assorted algebras.

I drew the two distinct sets of Schroeder paths—each set containing six paths—presented in A088617 and A060693 corresponding to the coefficient of the second order term

$$6t^2$$ in

$$c_4^r(t) =5t4+10t^3+6t^2+t$$,

which corresponds to the two terms

$$4m_3m_1+2m_2^2$$ in

$$c_4 =-5m_1^4+10m_2m_1^2-4m_3m_1-2m_2^2+m_4$$,

and saw that only two of the Schroeder paths in each set of six have a midline reflection symmetry, but I don't see how these paths can be mapped to the partitions, so my question to the users here, such as Gessel and Stanley, and their colleagues who are much more adept than I at constructing combinatorial/diagrammatic models is, again,

What are some combinatorial/diagrammatic models for the moment partition polynomials?

The (formal) Laurent series for the Riemann mapping

$$\mathit{LC}(z) = \frac{C(z)}{z} = \frac{1}{O(z)} = \frac{1}{M^{(-1)}(z)}= \frac{1}{z} + c_1+c_2z+c_3z^2+\cdots$$ $$= \frac{1}{z} + m_1+(m_2-m_1^2)z +(m_3 -3m_2m_1+2m_1^3)z^2 + \dotsb ,$$

has the (formal) compositional inverse

\begin{align*} \mathit{LC}^{(-1)}(z)=\mathit{LM}(z) = M(\frac{1}{z}) = O^{(-1)}(\frac{1}{z}) ={} & \frac{1}{z} + \; \frac{m_1}{z^2} + \; \frac{m_2}{z^3} +\;\frac{m_3}{z^4}+\dotsb \\ ={} & \frac{1}{z} + \; \frac{c_1}{z^2} + \; \frac{c_2 + c_1^2}{z^3} +\;\frac{c_3 + 3\; c_2c_1 + c_1^3}{z^4}+\dotsb. \end{align*}

Laurent series are the typical actors in most presentations of the theories of free probability and random matrices and are discussed in particular in He and Jejjala with respect to the $$q$$-expansion of Klein's $$j$$-invariant in relation to monster moonshine (cf. pp. 4, 6-7, 10-11, 14-15, 20-21, and 25). Laurent series of these types also play a role in applications in complex analysis of the Faber polynomials of symmetric function theory, (see A263916, in particular, McKay and his associates).

Alexandrov (p. 22) has two sets of Laurent series relations, both designated with $$f(z)$$ and $$\tilde{f}(z)$$, characterizing the actions of two subgroups of the Virasoro group—the first, for $$\mathit{VIR}_{+}$$ with $$f(z) = \mathit{LC}(\frac{1}{z})$$ and $$\tilde{f}(z) = \mathit{LC}^{(-1)}(\frac{1}{z})$$ with his $$b_{-n}$$, my $$c_n$$; the second, for $$\mathit{VIR}_{-}$$ with $$f(z) = \mathit{LC}^{(-1)}(\frac{1}{z})$$ and $$\tilde{f}(z) = \mathit{LC}(\frac{1}{z})$$ with his $$b_n$$, my $$m_n$$.

Multinomials for coefficients of the polynomials (added Feb. 19, 2022)

To generalize and reveal some otherwise hidden symmetry, incorporate an arbitrary nonzero $$m_0$$ and $$c_0$$ rather than imposing $$m_0=c_0=1$$ as in most formulations. Then each monomial summand in the partition polynomial for $$c_n$$ or $$m_n$$ has the form

$$d_0^{e_0}d_1^{e_1} ... d_n^{e_n}$$

for all the $$d_k$$ replaced by $$m_k$$ or all by $$c_k$$ with

$$(e_0+e_1+\cdots + e_n) = n+1$$

and

$$(0\cdot e_0+ 1\cdot e_1+ 2 \cdot e_2 + \cdots + n \cdot e_n) = n.$$

Theorem 2 on p. 9 of “Introduction to non-commutative probability” by Mottelson gives formulas with multinomial coefficients for the monomial summands of the moment and cumulant partition polynomials. The paper by Pielaszkiewicz et al. noted in my Jan. 16 comment below duplicates these formulas on p. 268. Comparison of these formulas with the related formula in A134264 gives the numerical coefficients of the monomials of the cumulant partition polynomials $$m_n$$ as

$$\frac{n!}{e_0! e_1!\cdots e_n!} =\frac{n!}{[n+1-(e_1+e_2+\cdots +e_n)]! \; e_1!\cdots e_n!} =\frac{n!}{[n-(k-1)]! \; e_1!\cdots e_n!}$$

with $$k = e_1+e_2+\cdots + e_n,$$

and for the monomials of the moment partition polynomials $$c_n$$,

$$\frac{(-n)!}{[-n-(k-1)]! \; e_1!\cdots e_n!} = (-1)^{k-1} \; \frac{(n+k-2)!}{(n-1)! \; e_1!\cdots e_n!} ,$$

using the identity $$\frac{(-x)!}{(-x-j)!} =(-1)^j \; \frac{(x-1+j)!}{(x-1)!}$$.

For example, consider the summand monomial $$-35\;m_1^3 m_2$$ of $$c_5$$; then, $$n=5$$, $$e_1=3$$, $$e_2=1$$, so $$k = e_1+e_2 =4$$, and

$$(-1)^{k-1} \frac{(n+k-2)!}{(n-1)!e_1!e_2!} = - \frac{7!}{4!3!1!} = -35 = \frac{(-n)!}{[-n-(k-1)]!\;e_1!e_2!} = \frac{(-5)!}{(-8)!3!1!} = \frac{(-5)(-6)(-7)(-8)(-9)\cdots}{[(-8)(-9)\cdots] \; 3!1!}.$$

For easy reference, the formulas in Mottelson, with $$Q_j =\left \{ (q_1, ..., q_j) \in \mathbb{N^j} \; | \; \sum_{i=1}^j \; q_i =n \right \}$$ are

$$c_n= m_n + \sum_{j=2}^n \; \frac{(-1)^{j-1}}{j} \; \binom{n+j-2}{j-1} \sum_{Q_j} m_{q_1}\cdots m_{q_j}$$

and

$$m_n= c_n + \sum_{j=2}^n \; \frac{1}{j} \; \binom{n}{j-1} \sum_{Q_j} c_{q_1}\cdots c_{q_j}.$$

Added June 13, 2023: Explicit multinomial expressions for all the partition polynomials in this entry are available in this MO-Q with $$m_n(c_1,...c_n) \to N_n(u_1,...,u_n)$$, $$c_n(m_1,...,m_n) \to N_n^{(-1)}(u_1,...,u_n)$$, and $$M^{(-1)}(x)/x \to A(x)$$.

• See also p. 77 of "Free convolution" by Bercovici in Free Probability and Operator Algebra edited by Voiculescu, Stammeier, and Weber for some discussion of the Laurent series compositional identity characterizing the free moments and cumulants. Jan 8, 2022 at 4:38
• Also see p. 197 of Lectures on the Combinatorics of Free Probability edited by Nica and Speicher, and pp. 270-2. Jan 8, 2022 at 5:29
• See a listing of the first five moment partition polynomials and a discussion of noncrossing partition combinatorics in “Cumulant-moment relation in free probability theory” by Pielaszkiewicz, von Rosen, and Singull ojs.utlib.ee/index.php/ACUTM/article/view/ACUTM.2014.18.22/… Jan 16, 2022 at 22:12
• Also p. 35 of "Three lectures in free probability" by Novak and LaCroix has the Laurent series presentation: arxiv.org/abs/1205.2097 Jan 24, 2022 at 19:14
• The formula for the numerical coefficients of the moment partition polynomials is in agreement with Corollary 3.13 on p. 12 of "Cumulants and convolutions via Abel polynomials" by Di Nardo, Petrullo, and Senato, arxiv.org/abs/1002.4803. Feb 21, 2022 at 6:16

The relation of the coefficients to the rising factorial allows three interpretations:

I) The upper. or rising, factorial (also sometimes called the Pochhammer symbol) occurs in the formula for the numerical coefficients for the moment partition polynomials $$c_n$$. A combinatorial interpretation of the rising facorial is given in "From sets to functions: Three elementary examples" (1981) by Joni, Rota, and Sagan:

Our third sequence is the upper factorial sequence

$$(x)^n=x(x+1)\cdots (x+n- 1)\;\;\;\;\;\;$$, $$n =0, 1,2,. . .$$ (2.3)

Unlike the first two sequences, these polynomials do not count functions. Instead, they count the number of dispositions from a set with $$n$$ objects to a set with $$x$$ objects. Dispositions can be visualized (occupancy interpretation) as all ways of placing $$n$$ distinguishable flags on $$x$$ distinguishable flagpoles. It is easy to see that $$(x)^n$$ counts all such arrangements: first we have $$x$$ choices of a flagpole for the first flag. If flag $$2$$ is on the same pole as flag $$1$$, then we can place it above or below flag $$1$$. Otherwise, it is on one of the $$x - 1$$ remaining poles. Thus there are $$x+ 1$$ choices for flag $$2$$. Similarly, there are $$x +2$$ choices for flag $$3$$ and, in general, $$(x + k - 1)$$ choices for flag $$k$$.

Translating their $$x$$ to our $$n-1$$ and their $$n$$ to our $$k$$, we have $$n-1$$ distinguishable flagpoles and $$k$$ flags, each flag of one color but with multiple flags having the same color with the multiplicity determined by $$e_1$$ to $$e_n$$. (Bookshelves and books are used on p. 55 of Combinatorics Through Guided Discovery by Bogart.)

II) Similarly, from the rising factorial polynomials--essentially the Stirling polynomials of the first kind---of OEIS A130534, an interpretation in terms of 'naturally grown' nonplanar rooted trees with colored trunks and nodes/vertices can be discerned.

III) The riising factorial polynomials are also presented in eqn. 1.6 on p.4 of "Meixner polynomials of the second kind and quantum algebras representing su(1,1)" by Hetyei, and so should allow an interpretation in terms of weighted Laguerre stories of Viennot.

IV) Edit: (Mar 13, 2023)

This identity between the rising factorials and the falling factorials is at the core of an iconic combinatorial reciprocity that can be traced through the work of Edelman (see Armstrong) and Rota, Sagan, and Jone (reffed above) around 1980 to Drew Armstrong, Athanasiadis, and Tzanaki (see refs in Armstrong's thesis "Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups") circa 2005, to the more the recent papers "Refined Lattice Path Enumeration and Combinatorial Reciprocity" (2022) by Mühle and Tzanaki and "Combinatorial reciprocity for non-intersecting paths" (2023) by Hopkins and Zaimi. These are related to the two sets of inversion polynomials in my question, which I have denoted $$[N]$$ and $$[N^{(-1)}] = [N]^{-1}$$, and a larger group algebra involving the associahedra polynomials $$[A^{(1)}] =[A]$$, the Schur self-Konvolution expansion polynomials $$[K] = [A^{(-1)}]$$, and extensions of these polynomials denoted, for $$m$$ any integer, by $$[N^{(m)}] = [N]^m$$ and $$[A^{(m)}]= [N]^m[A^{(0)}]$$--all addressed in several posts at my math blog. These papers then provide full combinatorial interpretations of $$[N]^{-1}$$ to the extent they address the full partition polynomials or partial interpretations.

• A ref for Viennot: imsc.res.in/~viennot/abjc3-ch5.html. Feb 21, 2022 at 18:49
• Slides by Viennot on weighted Laguerre histories:xavierviennot.org/coursIMSc2016/Ch_4_files/… Feb 21, 2022 at 18:55
• It's interesting that, in the distributional sense presented in mathoverflow.net/questions/382735/…, the rising factorials are the coefficients of the Laguerre series expansion of the Heaviside function and its derivatives, the derivatives of the Dirac delta function, while the falling factorials are the Laguerre expansion of the divided powers $x^n/n!$. Feb 22, 2022 at 19:21
• The generalized rook polynomials of Gessei should provide another model. Feb 22, 2022 at 23:09
• A closely associated operator is that of mathoverflow.net/questions/107159/… which could be generalized in the obvious manner. Feb 22, 2022 at 23:17