Revision f6d49571-b499-4558-8f1e-a4df168024d8

Two perspectives on families of m-ary trees. The second coincides with your formalism and provides two stages of generalization (and hints at a third). The first is related to comments by others.

**First perspective** on types of n-ary trees, **factorials and generalizations**:

$F_t(x) = (1-tx)^{-1/t} - 1$

is the e.g.f. for enumerating plane $m$-ary trees when $t=m-1$. OEIS [A094638][1] provides some examples when $t = \pm 1,\pm2,\pm3$ in my Dec. 15, 2007, comments. The e.g.f. is of importance for $t$ any real number.

For $t = 3$, the e.g.f. is

$F_3(x) = (1-3x)^{-1/3} - 1 = x + 4 x^2/2! + 28 x^3/3! + 280 x^4/4! + \cdots$,

generating the sequence [A007559][2], the right triple factorials, enumerating the number of increasing quaternary trees on n vertices.

For $t = -3$, the e.g.f. is

$F_{-3}(x) = (1+3x)^{1/3}-1 = x - 2x^2/2! + 10 x^3/3! - 80 x^4/4! + \cdots$,

generating the signed sequence [A008544][3], the left triple factorials, enumerating increasing plane (a.k.a. ordered) trees with n vertices (one of them a root labeled 1) where each vertex with outdegree r >= 0 comes in r+1 types (like an (r+1)-ary vertex).

Note the relation to multiplicative inversion:

$1+F_t(x) = 1/(1+F_{-t}(-x))$.

(I called this inversion, [A133314][4], the list partition transform, in the A094638 for historical reasons in my journey of discovery of its significance.)  

The compositional inverse (CI) plays a role also. The CI in $x$ of $G(x,t)$ about the origin $x=0$ of $F(x,t)$ is

$G(x,t)= [1-(1+x)^{-t}]/t$,

so the infinitesimal generator / Lie vector for generating $F(x,t)$ is

$g(x,t)\partial_x = \frac{1}{G'(x,t)}\partial_x = (1+x)^{t+1}\partial_x$;

that is,

$\exp[x g(z,t)\partial_z]  z |_{z=0}= F(x,t)$.

The Cayley analytic trees associated with the iterated operation

$(g(z)\partial_z)^n  z |_{z=0}$

for $t=\pm3$ are of the types described above (see. e.g., my "Mathemagical Forests" reffed in [A145271][5] along with the Bergeron et al. ref "Varieties of Trees" and my "Addendum to Mathemagical Forests" in A094638). (This is all related to the formalism of pre-Lie algebras.) 

My formulas in OEIS A094638, as pointed out therein and above, involve both compositional inversion and multiplicative inversion ([A133314][4]) and so are naturally related to Koszul duality as noted in the MO-Q "[Inversion, Koszul duality, combinatorics and geometry][6]". In fact, as I remarked in the formula section of A094638 and repeat above: With

$F(x,t) = (1-tx)^{-1/t} - 1$

an e.g.f. for the row polynomials $P(n,t)$ of A094638 with $P(0,t)=0$,

$G(x,t)= [1-(1+x)^{-t}]/t$

is the CI in $x$ about $x=0$. The case for $t=3$ is used in the proof of Corollary 4.2. of "Associator dependent algebras and Koszul duality" by Bremner and Dotsenko.

**Second perspective** on types of n-ary trees, **Euler-Fuss-Catalan numbers and generalizations**:

My comments on the relation between $[A^{(m)}]$ for $m \geq 1$ and the Fuss-Catalan numbers, generated by compositional inversion of $f(x) = x \pm x^{m+1}$ about $x=0$ (see, e.g., [A001764][7]), in my answer / extension to the MO-Q "[Infinite dimensional involutions: infinitely large sets of multivariate polynomials self-inverse under self-substitution][8]" (IDI) presents another perspective since $m$ is extended there to any integer. This is a generalization of the formalism of Novelli and Thibon in "[Hopf Algebras of m-permutations, (m+1)-ary trees, and m-parking functions][9]".


I have proved, in notes I'll soon post on my blog, that the partition polynomials presented in IDI naturally reduce to variants of the row polynomials of the triangles compiled in the table on p. 23 of "[On the inversion of Riordan arrays][10]" by Paul Barry and also discussed by N & T. Note the first columns of the coefficient triangles in the right column of the table for $m=-1,2,3,4$ contain variants of the Fuss-Catalan sequences,  A000108, [A000108][11] (again), [A001764][7], and [A002293][12]. This is because the full right triangles correspond to reductions to the non-vanishing partition polynomials of the compositional inversions of

$O^{(p)}(x) = x + c_1x^{p+1} + c_2x^{2p+1}+c_3x^{3p+1}+\cdots$

with $c_1 = \alpha$ and other $c_k =1$ (or equivalent reductions), which, in turn, reduces to

$O_{red}^{(p)}(x) = x + \alpha x^{p+1}$

for $c_k =0$ for $k>1$ giving the first columns of the triangles as coefficients (mod signs and index shifts) of the non-zero coefficients of $(O_{red}^{(p)}(x))^{(-1)}$, the generating fcts. for the aerated Fuss-Catalan sequences for $m \geq 2$.  

The right column of Barry's table contains natural reductions (mod signs and reversals of order of coefficients) of $[A^{(-2)}]$ for $m=-1$ to [A286784][13], $[A^{(-1)}]$ for $m=0$ to [A090181][14] / [A001263][15], $[A^{(0)}]$ for $m=1$ to [A007318][16], $[A^{(1)}]$ for $m=2$ to [A126216][17] / [A033282][18] / [A086810][19], $[A^{(2)}]$ for $m=3$ to [A243662][20] / [A102537][21], and $[A^{(3)}]$ for $m=4$ to [A24366][22]. In this light, the compositional inversion identity (CII) in item 11 of "[Guises of the noncrossing partitions (NCPs)][23]" appears as a generalization of your algebraic characterization of the o.g.f. of types of n-ary trees.
    
On Fuss-Catalan numbers and relations among their generating functions, see [Wikipedia][24] and also pages 33 and 34 of "[Connecting Scalar Amplitudes using The Positive Tropical Grassmannian][25]" by Cachazo and Umbert.

I've been a little too busy putting my notes with relevant proofs into pdfs to look at the explicit coefficients of $[A^{(m)}]$ for $m < -2$. However, Barry gives a formula in his table from which I computed the unsigned first columns of the triangles:

$a_n = \frac{1}{n+1} \binom{|m|(n+1)-1+n}{n}$

for $m=-2$ down, giving A006013, A006632, and A118971, which led to p. 19 of the ref "Some relatives of the Catalan sequence" by Liszewska and Młotkowski in A118971, through which this list continues as A130564, A130565, A234466, A234513, A234573, and A235340, consistent with spot checks by Barry's formula.

L & M start with the equation

$B_p(z) = 1 + zB_p(z)^p$ 

satisfied by

$B_p(z) = \sum_{n \ge 0}\frac{1}{n+1} \binom{np+1}{n} z^n$

and state that Lambert found

$B_p(z)^r = \sum_{n \ge 0}\frac{1}{np+r} \binom{np+r}{n} z^n$ 

valid even for $p$ and $r$ real. Then

$B_{-m}(z)^1 = \sum_{n \ge 0}\frac{1}{-mn+1} \binom{-mn+1}{n} z^n$

and using $\binom{-q}{n} = (-1)^n \binom{-q-1+n}{n}$,

$B_{-m}(z)^1 = \sum_{n \ge 0}(-1)^{n} \frac{1}{-mn+1} \binom{mn-1-1+n}{n} z^n$,

which yields the same sequence of absolute numbers as the formula I have from Barry, with a shift in the index (multiply by $z$ to get agreement). 

Letting $FC_p(z) = zB_p(z)$, the defining equation becomes

$FC_p(z) = z + (FC_p(z))^p$.

Then the compositional inverse satisfies  

$FC_p^{(-1)}(z) = z - z^p,$

and, for $p = 2,3,4,5$, this is the CI for the Fuss-Catalan sequences (aerated and signed) noted above--A000108, A001764, A002293, ... . 

For $p = 0, -1,-2,-3,...$, this is a Laurent series for which Example III of the MO-Q "Infinite dimensional involutions ..." applies to obtain the CI with $a_0 =1$, $a_{1-p} = -1$, and otherwise $a_k=0$. The partition polynomials of this example are those of [A355201][26] with a formula for their numerical coefficients and a combinatorial model for the formula in my pdf "One Matrix to Rule Them All ..." (link in the OEIS entry). 

I would search for other overarching combinatorial models in comments and refs in the pertinent OEIS entries, e.g., the ref "Multivariate Fuss-Catalan numbers" by Aval in A235340. I need some time to confirm the relationship to that article, and there's the ref "Coding of ordered trees" in A130564, to  which I have no access.   

As an overarching combinatorial construct for encompassing all the integers $m$ for the sets of partition polynomials $[A^{(m)}]$ (and $[N^{(m)}]$), I'd like to see a comprehensive theory of their relation to Feynman diagrams / Green functions in QFT since this is a common thread in discussions of the related triangles down to $m=-2$. Balduf, Yeats, Kreimer, their collaborators, and various other researchers have investigated this for $m >1$ as related to Schwinger-Dyson equations and Hopf algebras. N & T give also a more refined situation for which the indeterminates in the multivariate partition polynomials (at least for $m$ positive) are noncommutative. 

        

(Often the presence of negative integers in a generating function indicates some combinatorics of an underlying topological nature, such as Euler's formula for polytopes. This [MO-Q][27] contains another example of how natural it can be to extend $n$ in significant combinatorial sequences from the natural numbers to the full integers and retain combinatorial import. The Bernoulli numbers and $\zeta(n >1)$ are a good example of a sequence of numbers that can be negative and are not even integral that have connections with very important combinatorial models.) 

  


  [1]: https://oeis.org/A094638
  [2]: https://oeis.org/A007559
  [3]: https://oeis.org/A008544
  [4]: https://oeis.org/A133314
  [5]: https://oeis.org/A145271
  [6]: https://mathoverflow.net/questions/194888/inversion-koszul-duality-combinatorics-and-geometry
  [7]: https://oeis.org/A001764
  [8]: https://mathoverflow.net/questions/422539/infinite-dimensional-involutions-infinitely-large-sets-of-multivariate-polynomi
  [9]: https://arxiv.org/abs/1403.5962
  [10]: https://arxiv.org/pdf/2101.06713.pdf
  [11]: https://oeis.org/A000108
  [12]: https://oeis.org/A002293
  [13]: https://oeis.org/A286784
  [14]: https://oeis.org/A090181
  [15]: https://oeis.org/A001263
  [16]: https://oeis.org/A007318
  [17]: https://oeis.org/A126216
  [18]: https://oeis.org/A033282
  [19]: https://oeis.org/A086810
  [20]: https://oeis.org/A243662
  [21]: https://oeis.org/A102537
  [22]: https://oeis.org/A243663
  [23]: https://mathoverflow.net/questions/338905/guises-of-the-noncrossing-partitions-ncps
  [24]: https://en.wikipedia.org/wiki/Fuss%E2%80%93Catalan_number
  [25]: https://arxiv.org/abs/2205.02722
  [26]: https://oeis.org/A355201
  [27]: https://mathoverflow.net/questions/412573/combinatorics-for-the-action-of-virasoro-kac-schwarz-operators-partition-poly