Skip to main content
13 of 23
Undeleted and revamped
Tom Copeland
  • 10.5k
  • 3
  • 57
  • 84

Revamped extended comment, 3/20/23:

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.

As you state in your comment, for $n= 3$, the solution is the $(2)$-Fuss-Catalan sequence of numbers OEIS A001764 = (1,1,3,12,55,...) . These are the absolute values of the coefficients of the top order monomials $u_1^n$, the diagonals, of the set of $(2)$-associahedra partition polynomials $A^{(2)}_n(u_1,u_2...,u_n)$ that are the coefficients of the compositional inverse

$$(O^{(2)}(z))^{(-1)} = z + A_1(u_1)z^{2 \cdot 1+1} + A_2(u_1,u_2) u_2 z^{2\cdot 2 +1} + A_3(u_1,u_2,u_3) u_3 z^{2\cdot 3 +1} + \cdots.$$

of the odd o.g.f.

$$O^{(2)}(z) = z + u_1z^{2 \cdot 1+1} + u_2 z^{2\cdot 2 +1} + u_3 z^{2\cdot 3 +1} + \cdots.$$

The absolutes values of the sum of the signed coefficients of the polynomials of $[A^{(2)}]$ give A000108 = (1,1,2,5,14, ...), the Catalans.

For $m$ any integer, there is a ladder of sets of $(m)$-noncrossing partitions / $(m)$-Narayana polynomials, $[N^{(m)} = [N]^m$, dual to the $(m)$-associahedra polynomials, $[A^{(m)}]$. The duals are characterized by the generalized face-h-polynomial substitution identity / raising-lowering identity

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

or, conversely,

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

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

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

This f-h identity implies that summing the coefficients of one set gives the diagonals of the other set.

And, indeed, summing the coefficients of the dual set $[N^{(2)}]$ generates the $(2)$-Fuss-Catalan sequence and the diagonal is A000108.

The set $[A^{(2)}]$ can be generated by the Lagrange inversion formula; e.g., using Wolfram Alpha online,

$A^{(2)}_4 = −u_4 + 10 u_1 u_3 + 5 u_2^2 − 55 u_1^2 u_2 + 55 u_1^4 $

is generated by

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

and

$N^{(2)}_4 = 14 u_1^4 + 28 u_2 u_1^2 + 8 u_3 u_1 + 4 u_2^2 + u_4$

is generated by

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

For $m=-2$, simply replace in an obvious fashion the $2$ in the formulas above with $-2$ to obtain (with compositional inversion away from the origin, i.e., about the the point at infinity) the $(-2)$-Fuss-Catalan sequence of numbers (1,A000108) =(1,1,1,2,5,14,...); e.g., a generalized Lagrange inversion formula gives

$A^{(-2)}_4 = - (5 u_1^4 + 15 u_2 u_1^2 + 6 u_3 u_1 + 3 u_2^2 + u_4)$

is generated by

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

and

$N^{(-2)}_4 = -30 u_1^4 + 36 u_2 u_1^2 - 8 u_3 u_1 - 4 u_2^2 + u_4$

is generated by

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

The absolutes values of the sum of the signed coefficients of the polynomials of $[A^{(-2)}]$ give (1, A006013) = (1,1,2,7,30,143, ...). The absolute values of the sum of the signed coefficients of the polynomials of $[N]^{-2}$ give (1,A000108) = (1,1,1,2,5,14,...), the shifted Catalan numbers. The absolutes of the diagonals of $[N]^{-2}$ give (1, A006013).

For $m=-3$, the absolutes of the diagonals of $[A^{(-3)}]$ are (1,A006013) =(1,1,2,7,30,143,...), the $(-3)$-Fuss-Catalan sequence of numbers. The absolute sums of the coefficients of $A^{(-3)}_n(u_1,...,u_n)$ give the $(-3)$-Fuss-Narayana sequence $(1,[A006632][5]) = (1,1,3,15,91,612, ...)$ as do the 'diagonals' of $[N^{(-3)}]$ whereas the absolutes of the sums of $[N^{(-3)}]$ are (1, A006013).

For any integer $m$, 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}} .$

Examples:

$[A^{(2)}]$, reduced is A243662 and A102537

$A^{(2)}_3 = -u_3 + 8 u_1 u_2 - 12 u_1^3$

second derivative [(1+(1+t)x)(1+x)^2]^3 / 3! at x = 0 is 12 + 8t + t^3

second derivative [(1+(1+t)x)(1+tx)^2]^3 / 3! at x = 0 is 1 + 8t + 12t^2.

$[A^{(-2)}]$, reduced is A286784

$A^{(-2)}_3 = - (2 u_1^3 + 4 u_2 u_1 + u_3) $

second derivative [(1+(1+t)x)(1+x)^(-2)]^3 / 3! at x = 0 is t^2 - 4 t + 2

second derivative [(1+(1+t)x)(1+tx)^(-2)]^3 / 3! at x = 0 is 2 t^2 - 4 t + 1.

The generalized f-h identity inplies

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

so

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

Examples:

$[N]^2$, reduced is A120986 and A108767

$N^{(2)}_3 = u_3 + 6 u_1 u_2 + 5 u_1^3$

second derivative [(1+tx)(1+x)^2]^3 / 3! at x = 0 is 5 + 6 t + t^2

second derivative [(1+x)(1+tx)^2]^3 / 3! at x = 0 is 1 + 6 t + 5 t^2

$N^{(-2)}_3 = 7 t^3 - 6 t^2 + t$ $

second derivative [(1+tx)(1+x)^(-2)]^3 / 3! at x = 0 is t^2 - 6 t + 7

second derivative [(1+x)(1+tx)^(-2)]^3 / 3! at x = 0 is 7 t^2 - 6 t + 1

The coefficients of these polynomials are gleaned from the formulas on page 15 of "On the enumeration of positive cells in generalized cluster complexes and Catalan hyperplane arrangements" by Athanasiadis and Tzanaki.

At every level of refinement or coarseness--from the coefficients of the partition polynomials to those of their reductions--the analytic formulas remain immutable. For a leap from positive to negative integers for $m$, the iconic rising-to-falling factorials polynomial identity

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

account for apparent variation in the formulas--as above, so below. Drake addresse this in the section 1.10 Numerator polynomials beginning on p. 58 of his thesis "An inversion theorem for labeled trees and some limits of areas under lattice paths".

The combinatorial interpretations of the $(m)$-Fuss-Catalan and the $(m)$-Fuss-Narayana sequences of numbers are then open to the broader ones of the more refined characters, the $(m)$-associahedra and $(m)$-noncrossing partitions and their polynomial reductions.

Athanasiadis and Tzanaki (link above) give some geometric interpretations for the coefficients of the reduced polynomials for $m$ any integer as does Drew Armstrong in his thesis "Generalized Noncrossing Partitions and Combinatorics of Coxeter Groups" and Muhle and Tzanaki in "Refined Lattice Path Enumeration and Combinatorial Reciprocity". Song's ref in A173020 should lead to others for $m > 0$. Several articles by Novelli and Thibon (e.g., one and two) address $m >0$. The combinatorics are rife with trees, lattice paths, dissected polygons, Feynman diagrams, . . . (see A134264 for $[N]$; A133437. differently normalized $[A]$; A354622, $[N]^2$; and A286784, a reduction of $[A^{(-2)}]$.

(See the intro to “Why Delannoy numbers?” by Bandererier and Schwer on some history of the associated names (they ref Stanley in turn)--in particular, Runyon numbers enumerate Dyck paths and noncrossing partitions.

Tom Copeland
  • 10.5k
  • 3
  • 57
  • 84