A combinatorial interpretation for $n$-ary trees for negative $n$

Question

The ordinary generating function $T_n=T_n(x)$ for the $n$-ary trees satisfies the functional equation $$ T_n=1+xT_n^n. $$ This is usually defined for $n\ge 0$, but the functional equation can be extended to negative $n$. Writing $$ T_{-n}=1+xT_{-n}^{-n} $$ and dividing through by $T_{-n}$, we obtain that $$ T_{-n}^{-1}=1-x(T_{-n}^{-1})^{n+1}, $$ i.e. $$ T_{-n}(x)=\frac{1}{T_{n+1}(-x)}. $$ What would be a natural way to interpret this combinatorially? I.e. what are "$n$-ary trees" for negative $n$, why do we get the extra $1$ degree, etc.

Answer 1

Here's an explanation of the combinatorial meaning of $T_{-n}(x)$.

The combinatorial interpretation $T_n(x)$ is that it counts $n$-ary trees. More precisely, it counts ordered trees in which every vertex has 0 or $n$ children, and each internal vertex (with $n$ children) is weighted $x$ and each leaf is weighted 1. Let's mark each edge from a vertex to its $i$th child with $i$, and then delete all the leaves (together with their incident marked edges). The original tree can easily be reconstructed from this reduced tree. What we now have is an ordered tree in which the edges from each vertex to its children are marked with some subset of $[n]=\{1,2,\dots,n\}$ in increasing order from left to right.

If we remove all the marks we obtain an underlying ordered tree. Given an ordered tree, how many ways are there to mark it to obtain a tree counted by $T_n(x)$? For each vertex with $k$ children, we can assign marks to the edges to its children in $\binom{n}{k}$ ways. So for an ordered tree with $m$ vertices, if the numbers of children of the vertices are $k_1,k_2,\dots, k_m$ then the number of ways of marking this tree is $\binom{n}{k_1}\binom{n}{k_2}\cdots \binom{n}{k_m}$. So the coefficient of $x^m$ in $T_n(x)$ is the sum of these products of binomial coefficients over all ordered trees on $m$ vertices. If $m>0$ and we replace $n$ by $-n$ this product of binomial coefficients becomes $$\binom{-n}{k_1}\binom{-n}{k_2}\cdots \binom{-n}{k_m}=(-1)^{m-1}\binom{n+k_1-1}{k_1}\binom{n+k_2-1}{k_2}\cdots \binom{n+k_m-1}{k_m},$$ since $k_1+\cdots +k_m = m-1$. But $\binom{n+k-1}{k}$ is the number of ways of marking the edges from a vertex to its $k$ children with elements of $[n]$ so that the marks are weakly increasing from left to right, but with repeated marks allowed. Thus $1-T_{-n}(-x)$ counts ordered trees (with at least one vertex) in which the edges joining each vertex to its children are marked with elements of $[n]$ so that the marks are weakly increasing from left to right. I'll call these trees $n$-colored trees. (Such trees have appeared in various places in the literature; the only reference I can recall offhand is to a paper of mine and S. Seo, A refinement of Cayley's formula for trees.)

Thus if we set $U_n(x) = 1-T_{-n}(-x)$ then $U_n(x)$ is the generating function for nonempty $n$-colored trees. It is also not hard to prove this algebraically. In the defining equation $T_{-n}(x) =1-xT_{-n}(-x)^{-n}$, we replace $T_{-n}(x)$ with $1-U_n(x)$ and we obtain $$U_n(x) =\frac{x}{\bigl(1-U_n(x)\bigr)^n}$$ from which the combinatorial interpretation of $U_n(x)$ is clear.

Alex's identity $$ T_{-n}(x)=\frac{1}{T_{n+1}(-x)} $$ may be rewritten as $$T_{n+1}(x)=\frac{1}{1-U_n(x)}.$$ I'm sure that there is a reasonably straightforward bijective proof of this identity, but I didn't work it out. (This post is long enough!)

Answer 2

Added Apr. 23, 2023: More interpretations of these sequences of numbers are provided in my blog post "Interpretations of the (−m)−Fuss-Narayana numbers for m>0".

Added Apr. 10, 2023: (a new combinatorial interpretation and an Ehrhart reciprocity)

(For $n,m$ natural numbers, i.e., $1,2,3,\cdots$.)

As shown by Hilton, Holton, and Pedersen, in refs. 10 and 11 below, the number of paths that lie below the line $y = (m-1)x$ from the point $(1,0)$ in the Cartesian plane, via horizontal and vertical steps only, to the point $(n,(m-1)n-1)$ is

$${}_m d_{1n} = \frac{m-1}{mn-1} \binom{mn-1}{n-1}.$$

(Hilton and Pedersen call these p-good paths--a poor choice of names, I prefer m-good.)

As I indicate below, the absolute values of the $(-m)$-Fuss-Narayana numbers, $[FFN^{(-m)}]$, the sequences of numbers defined by your $T_{-m}$, are given by

$$|FFN_n^{(-m)}| = | \frac{1}{-mn+1} \binom{-mn+1}{n} | = \frac{1}{mn-1} \binom{(m+1)n-2}{n} ,$$

implying

$$|FFN_n^{(-m+1)}| = \frac{1}{(m-1)n-1} \frac{(mn-2)!}{n!((m-1)n-2)!} = \frac{(mn-2)!}{n!((m-1)n-1)!} ={}_m d_{1n} . $$

Examples:

For $n\geq1$, ${}_2 d_{1n}$ are $(1,1,2,5,14,42,...)=$ A000108, and for $n \ge 0$, $|[FFN^{(-1)}]| =(1,A000108).$

For $n\geq1$, ${}_3 d_{1n}$ are $ (1,2,7,30,143,...) =$ A006013, and for $n \ge 0$, $|[FFN^{(-2)}]| =(1,A006013).$

For $n\geq1$, ${}_4 d_{1n}$ are $(1,3,15,91,612,...)=$ A006632, and, for $n \ge 0$, $|[FFN^{(-3)}]| =(1,A006632).$

For $m > 0$, what I denote as the absolutes of the free $(-m)$-Fuss-Narayana numbers $|FFN_n^{(-m)}|$ are called the positive Fuss-Catalan numbers on p. 9 of M & T (ref. 6 below). What M & T call the (reverse) positive Fuss-Narayana numbers are what I identify below as the absolute coefficients of the mono-variate $(-m)$-Fuss-Catalan polynomials $TA_n^{(-m)}$, whose sums, as well as those of its refinement, the multi-variate $(-m)$-Fuss-Catalan ParPs $A_n^{(-m)}(u_1,...,u_n)$, are $|FFN_n^{(-m)}|$. Accordingly, $N_{m,n,1}(x,0)$ in M & T is my $TA_n^{(-m)}(x)$ below. The fact that $(RTN^{(m+1)}(x,0))^{(-1)} = (RTA^{(m)}(x,0))^{(-1)}$ is a source of conflation, but the algebraic and combinatorial formulation via the multivariate partition polynomials sorts this out, justifying, in my mind, the break with the historically motivated terminology of M & T and being more in line with that of Novelli and Thibon. With this difference in perspectives in mind, Ehrhart reciprocity in relation to these numbers is discussed on p. 28 of M & T.

(For $[FFN^{(m)}]$ with $m \geq 1$, a Dyck path interpretation is available as in A125181 as well as ordered trees. A130564 is $|[FFN^{(-5)}]|$, which has a link to an article on ordered trees.)

Revamped extended comment, 3/21/23: (An iceberg in a big nutshell)

The initial eqn.

$$T_n=1+xT_n^n$$

is eqn. 6.3 on p. 449 of "Functional composition patterns and power series reversion" by Raney (see ref 5 below also), and you comment that the solution for $n = 3$ is OEIS A001764 and for $m=-3$, a variant of A006632.

Finally, I've identified this dual pair in a broader scheme in which the Fuss-Catalan (FC) number sequences and the Fuss-Narayana (FN) number sequences are embedded. The larger perspective preserves the reciprocity / duality between positive and negative indices and allows for more diverse combinatorial interpretations.

The following are the first few of the set $[N^{(3)}]$ of $(3)$-noncrossing partitions / $(3)$-Narayana partition polynomials (ParPs):

$N^{(3)}_0 = 1$

$N^{(3)}_1 = u_1$

$N^{(3)}_2 = 3 u_1^2 + u_2$

$N^{(3)}_3 = 12 u_1^3 + 9 u_2 u_1 + u_3$

$N^{(3)}_4 = 55 u_1^4 + 66 u_2 u_1^2 + 12 u_3 u_1 + 6 u_2^2 + u_4$.

The 'diagonal', i.e., coefficients of the $u_1^n$ monomials, appearing as the first column in this depiction, is (1,1,3,12,55,...) = A001764. Call these the $(3)$-Fuss-Narayana numbers. The sums of the coefficients are (1,1,4,22,140,969,...) = A002293, the $(3)$-Fuss-Catalan numbers. Be aware that A001764 is also the $(2)$-FC sequence.

The following are the first few of the set of $(-3)$-noncrossing partitions / $(-3)$-Narayana $[N^{(-3)}]$ ParPs:

$N^{(-3)}_0 = 1$

$N^{(-3)}_1 = u_1$

$N^{(-3)}_2 = - 3 u_1^2 + u_2 $

$N^{(-3)}_3 = 15 u_1^3 - 9 u_2 u_1 + u_3$

$N^{(-3)}_4 =-91 u_1^4 + 78 u_2 u_1^2 - 12 u_3 u_1 - 6 u_2^2 + u_4$

The 'diagonal', i.e., coefficients of the top order monomials, appearing as the first column in this depiction, is (1,1,-3,15,-91,612,...) = signed (1,A006632). Call these the $(-3)$-Fuss-Narayana numbers. The row sums with all $u_k =1$ are (1,1,-2,7,-30,143,...) = signed (1, A006013), the $(-3)$-Fuss-Catalan numbers.

There is the following duality between the $(\pm 3)$-noncrossing ParPs and the $(\pm 3)$-associahedra ParPs, a generalized face-h-polynomial identity, under substitution of one set (on the right) of ParPs into another (on the left);

$$[A^{(\pm 3)}] = [N^{(\pm 3)}][R]$$

and

$$[A^{(\pm 3)}][R] = [N^{(\pm 3)}],$$

where $[A^{(0)}] =[R]$ is the set of reciprocal partition polynomials that can be defined by the shifted reciprocal of an o.g.f. as

$$\frac{x}{O(x)} = \frac{1}{1+u_1x +u_2 x^2 + u_3 x^3+\cdots} = \sum_{n \geq 0} R_n(u_1,...,u_n) x^n.$$

It is this duality that underlies the relation between the diagonals of $[N^{(\pm3)}]$ and the row sums of coefficients of $[A^{(\pm 3)}]$ and the converse.

Added facets of the iceberg, April 5, 2023: (Start)

Cluster complexes and illustration of $[A^{(m)}]-[N^{(m)}]$, or generalized face-h-polynomial, duality:

"Cataland: Why the Fuss?" by Stump, Thomas, and Williams has an illustration on p. 101 (Fig. 25) of four cluster complexes associated with $N^{-3}_4$ with $91$ facets, $N^{-3}_5$ with $612$ facets, $N^{-2}_4$ with $30$ facets, and $N^{-2}_5$ with $143$ facets. The number of facets are the unsigned coefficients of the diagonals, i.e., the absolute coefficients of the monomials $u_1^n$, of $N^{(m)}_n(u_1,...,u_n)$, equal to the unsigned sums of the coefficients of $A^{(m)}_n(u_1,...,u_n)$; e.g.,

$A^{(-3)}_4 = - (30 u_1^4 + 45 u_2 u_1^2 + 10 u_3 u_1 + 5 u_2^2 + u_4).$

(7/27/2024: An unsigned reduction of $[A^{(-3)}]$ is Table 4 on pg. 18 of "A Subfamily of Skew Dyck Paths Related to k-ary Trees" by Zhang & Zhuang, and that for $[A^{(-2)}]$ is Table 3 on Pg. 17.)

Again, the signed $(-3)$-Fuss-Narayana numbers associated with $[N]^{-3}$ are (1,1,-3,15,-91,612.,...) = signed (1, A006632) and for $[N]^{-2}$, (1,1,-2,7,-30,143,...) = signed (1, A006013). Tree and other models are presented in the OEIS entries for these Fuss-Narayana numbers.

(End)

The $[N^{\pm 3}]$ are generated by the generalized Lagrange inversion formula (a special Lagrange-Schur-Jobotinsky identity); e.g.,

$N^{(3)}_4 = 55 u_1^4 + 66 u_2 u_1^2 + 12 u_3 u_1 + 6 u_2^2 + u_4$

is generated by (cut-and-paste into Wolfram Alpha online) the $3\cdot 4 =12$th derivative

twelfth derivative (1/(3 \cdot 4)!) (1 + u_1x^(3 \cdot 1) + u_2x^(3 \cdot 2) + u_3x^(3 \cdot 3) + u_4x^(3 \cdot 4))^((3 \cdot 4+1)) / (3 \cdot 4+1) at x = 0,

and

$N^{(-3)}_4 =-91 u_1^4 + 78 u_2 u_1^2 - 12 u_3 u_1 - 6 u_2^2 + u_4$

is generated by

twelfth derivative (1/(3 \cdot 4)!) (1 + u_1x^(3 \cdot 1) + u_2x^(3 \cdot 2) + u_3x^(3 \cdot 3) + u_4x^(3 \cdot 4))^((-3 \cdot 4+1)) / (-3 \cdot 4+1) at x = 0.

The same applies with $-3$ exchanged for any integer $m$ to generate any $[N^{(m)} ]$. In addition $[N^{(m)}] = [N]^{m}$; that is, $[N^{(m)}]$ for $m > 0$ is generated by iterated self-substitution of $[N^{(1)}] = [N]$ into itself and likewise for $m < 0$ w.r.t. to $[N^{(-1)}] = [N]^{-1}$, or start at any $[N]^p$ and go up with $[N]$ or down with $[N]^{-1}$. There are other veiled relationships as well.

The generalized Lagrange inversion formulas for generating $[A^{(m)}]$ are the same as for $[N^{(m)}]$ with a fairly obvious change of signs.

The coefficients of $[N]$ and $[N]^{-1}$ are related by the iconic rising-to-falling-factorials polynomial identity

$$n! \binom{-q}{n} =(-1)^n n! \binom{q-1+n}{n}.$$

See this MO-Q for explicit formulas with $NCP_n$ there being $N_n$ here and $c_n$ there, $N^{(-1)}_n$ here. Another manifestation of this reciprocity, one could say the source, depending on the starting point of derivations, is that the generalized Lagrange inversion formulas that generate both $[N^{(m)}]$ and $[A^{(m)}]$ involve binomial expansions for the same expression or its aerated variant with basically only sign changes in the exponent. Below we'll see this reflected in another characterization via dual power and Laurent series. (Combinatorial aspects with regard to tree models are discussed in Drake, see refs below.)

This central reciprocity is inherited by natural reductions of the ParPs to single variable polynomials via letting, e.g., $u_k = t$ for all $k$ and by the row sums of the coefficients and the diagonals.

So, as the positive integers are greater than the negative integers, the refinements are 'higher' than the coarser reductions, and numerators are above denominators, in these senses, we can say "As above, so below" or with the pun "As $A_n$bove, so below" since the associahedra and noncrossing partitions are so intimately linked with the $A_n$ Weyl-Coxeter group.

For any integer $m$, variants for the reduced polynomials of $[A^{(m)}]$ are the coefficients of the compositional inverse about $x=0$ of

$(RTA^{(m)}(x,t))^{(-1)} = \frac{x}{(1+(1+t)x)(1+x)^{m}}$

or

$(TA^{(m)}(x,t))^{(-1)} = \frac{x}{(1+(1+t)x)(1+tx)^{m}} ,$

and the generalized f-h identity implies the same for variants of the reduced $[N^{(m)}]$

$(RTN^{(m)}(x,t))^{(-1)} = \frac{x}{(1+tx)(1+x)^{m}} $

or

$(TN^{(m)}(x,t))^{(-1)} = \frac{x}{(1+x)(1+tx)^{m}}.$

$[N]^{3}$ reduces to A173020. $[A^{(3)}]$ reduces to A243663. No reductions of $[N]^{-3}$ nor $[A^{(-3)}]$ are in the OEIS. These are reductions mod signs and shifts in the polynomials--just compare with the ParPs for precise relationships.

The symmetry / reciprocity / duality--the interchange of $-m$ for $m$ and others--among the formulas is reflected in the series whose compositional inversions characterize $[A^{(m)}]$ and $[N^{(m)}]$: for $m$ any integer but $0$,

$$O^{(m)}(z) = z \;(1 + u_1z^{m} +u_2z^{2m} + u_3z^{3m} + \cdots)$$

and

$$(O^{(m)}(z))^{(-1)} = z\;(1 + A^{(m)}_1(u_1)z^{m} +A^{(m)}_2(u_1,u_2)z^{2m} + A^{(m)}_3(u_1,u_2,u_3)z^{3m} + \cdots)$$

$$ =z\;(1 + N^{(m)}_1(R_1(u_1))z^{m} +N^{(m)}_2(R_1(u_1),R_2(u_1,u_2))z^{2m} + \cdots).$$

This implies that the $[A^{(m)}]$ for $m > 1$ are 're-indexed samplings' of the components of $[A]$ (i.e., with components periodically zeroed out) and likewise for $[A^{(m)}]$ for $m < 1$ w.r.t. $[A^{(-1)}]$. The same applies for $[N^{(m)}]$.

---

---

The following papers are pertinent;

1. "Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups" by Armstrong: Geometric interpretations of his 'positive' Catalan numbers.

2. "On the enumeration of positive cells in generalized cluster complexes and Catalan hyperplane arrangements" by Athanasiadis and Tzanaki: The coefficients of the reduced polynomials for any integer $m$ are gleaned from the formulas on page 15 and they give some geometric interpretations for the coefficients of the reduced polynomials.

3. "On the inversion of Riordan arrays" by Barry: Versions of reduced $[A^{(p)}]$ from $p=-2$ (his $m = -1$) to $p =3$ on p. 23 in the last column of the table.

4. "An inversion theorem for labeled trees and some limits of areas under lattice paths" by Drake: Section 1.10 Numerator polynomials beginning on p. 58 has discussion of combinatorial reciprocity and tree models.

5. "Some relatives of the Catalan sequence" by Liszewska and Młotkowski: The 'Fuss number sequences' on pg. 19 is a list of the $(-|m|)$-Fuss-Narayana numbers beginning with $m=1$, A000108, A006013, A006632, whose o.g.f.s satisfy $zB(z) =\frac{z}{(1-zB(z))^{p-1}}.$

6. "Refined Lattice Path Enumeration and Combinatorial Reciprocity" by Muhle and Tzanaki: Geometric interpretations.

7. "Hopf Algebras of m-permutations, (m+1)-ary trees, and m-parking functions" by Novelli and Thibon: Fig. 13 on p. 46 is a list of $FC$ sequences, beginning with $m=1$, A000108, A001764, A002293. Page 43 has variants of the reduced triangles for $[N]$, $[N]^2$ and $[N]^3$. Combinatorial interpretations for $m$ positive.

8. "Noncommutative Symmetric Functions and Lagrange Inversion II: Noncrossing partitions and the Farahat-Higman algebra" by Novelli and Thibon: Combinatorial interpretations for $m > 0$, but also $[N^{(-1}]$. Another refinement with noncommutative indeterminates.

9. “Catalan numbers, parking functions, permutahedra, and noncommutative Hilbert schemes” by Lunts, Spenko, and Van den Bergh: the Fuss-Narayana numbers are called the Fuss-Catalan numbers in Corollary 1.3 on pg. 2.

10. "Mathematical Vistas: From a room with many mirrors" by Hilton, Holton, and Pedersen (see p. 221)

11. "Catalan Numbers, Their Generalization, and Their Uses" by Hilton and Pedersen