DIAGONALS OF TRIANGLES WITH GENERATING FUNCTION EXP(t*F(x)).


There are several triangular arrays in the database whose e.g.f. has
the form exp(t*F(x)), where F(0) = 0. These include polynomial
sequences of binomial type such as the falling factorials A008275,
the Bell polynomials A008277, the Abel polynomials x*(x+n)^(n-1),
essentially A061356, and the triangle of Lah numbers A008297.
Following Drake we show that the generating function for the
triangular array read by diagonals is the compositional inverse with
respect to x of (x-t*F(x)).

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Let F(x) be a formal power series

	F(x) = f(1)*x + f(2)*x^2/2! + f(3)*x^3/3! + ....

Define A(n,k) by

	F(x)^k/k! = sum {n >= k} A(n,k)*x^n/n!.

Clearly, A(n,k) = 0 when k > n. Hence the function

	exp(t*F(x)) = sum {k >= 0} t^k*F(x)^k/k!

		    = sum {n,k >= 0} A(n,k)*t^k*x^n/n!

is the e.g.f. for the lower triangular array (A(n,k))n,k>=0:

.n\k.|.....0........1........2...
= = = = = = = = = = = = = = = = =
..0..|...A(0,0)
..1..|...A(1,0)...A(1,1)
..2..|...A(2,0)...A(2,1)...A(2,2)
...

If the coefficient f(1) is nonzero the rows of this triangle are the
coefficients for a polynomial sequence of binomial type. Let

	d(n,t) = sum {k >= 0} A(n+k-1,k)*t^k

denote the o.g.f. for the n-th diagonal of the triangle (n = 1
corresponding to the main diagonal). Then the exponential generating
function for the triangle read by diagonals is

	sum {n >= 1} d(n,t)*x^n/n!.

In [1], Drake shows that d(n,t) is a rational function of the form
p(n,t)/(1-f(1)*t)^(2n-1), where p(n,t) is a polynomial of degree at
most n-1. If further f(1) = 0 then d(n,t) = p(n,t) is a polynomial
for all n.
Implicit in Drake 1.10 is the fact that the generating function by
diagonals sum {n >= 1} d(n,t)*x^n/n! is equal to the compositional
inverse (with respect to x) of the function (x-t*F(x)). For the
convenience of the reader we give a slightly modified version of
Drake's proof in Proposition 1. We require the Lagrange inversion
formula, which we state in the following form:

LAGRANGE INVERSION FORMULA

Let H(x) = h(1)*x + h(2)*x^2 + ... be a formal power series with
h(1) <> 0. The compositional inverse H^(-1)(x) has the expansion

	H^(-1)(x) = sum {n >= 1} c(n)*x^n,

where

	c(n)= 1/n * coefficient of x^(n-1) in (x/H(x))^n.

PROPOSITION 1

Let F(x) be a formal power series

	F(x) = f(1)*x + f(2)*x^2/2! + f(3)*x^3/3! + ...,

and let (A(n,k))n,k>=0 be the lower triangular array with e.g.f.
exp(t*F(x)).
Let

	d(n,t) = sum {k >= 0} A(n+k-1,k)*t^k

denote the o.g.f. for the n-th diagonal of the triangle.
Let D(x,t) = (x-t*F(x)). Then D^(-1)(x,t), the compositional inverse
of D with respect to x, is the e.g.f. for the diagonals of the
triangle (A(n,k)); that is,

	D^(-1)(x,t) = sum {n >= 1} d(n,t)*x^n/n!.

PROOF

By the Lagrange inversion formula

	D^(-1)(x,t) = sum {n >= 1} c(n)*x^n,

where

	c(n) = 1/n * coefficient of x^(n-1) in (x/D(x,t))^n.

By the binomial theorem

	(x/D(x,t))^n = 1/(1-t/x*F(x))^n

		     = sum {k >= 0} (t/x)^k*binomial(n+k-1,k)*F(x)^k.

Hence

	c(n) = 1/n*sum {k >= 0} t^k*{coefficient of x^(n+k-1) in
		binomial(n+k-1,k)*F(x)^k}

	     = 1/n*sum {k >= 0} t^k*binomial(n+k-1,k)*k!*1/(n+k-1)!
	     	*A(n+k-1,k)

	     = 1/n!*sum {k >= 0} t^k*A(n+k-1,k)

	     = d(n,t)/n!.

Thus
	D^(-1)(x,t) = sum {n >= 1} c(n)*x^n

		    = sum {n >= 1} d(n,t)*x^n/n!.

EXAMPLES

1) F(x) = log(1+x). D(x,t) = x - t*log(1+x).

The function exp(t*F(x)) = (1+x)^t is the e.g.f. for A008275, the triangle
of Stirling numbers of the first kind. By proposition 1,the e.g.f. for the
diagonals of A008275 is equal to

	D(x,t)^(-1) =  (x-t*log(1+x))^(-1)

		    = x/(1-t) - t/(1-t)^3*x^2/2! + (2*t+t^2)/(1-t)^5*x^3/3!

		    - (6*t+8*t^2+t^3)/(1-t)^7*x^4/4! + ....

The coefficients of the numerator polynomials are listed in A112007.

2) F(x) = exp(x)-1. D(x,t) = x-t*(exp(x)-1)).

The function exp(t*F(x)) is the e.g.f. for A008277, the triangle of
Stirling numbers of the second kind. By proposition 1, the e.g.f.
for the diagonals of A008277 is

	D(x,t)^(-1) = (x-t(exp(x)-1))^(-1)

	            = x/(1-t) + t/(1-t)^3*x^2/2! + (t+2*t^2)/(1-t)^5*x^3/3!

	           + (t+8*t^2+6*t^3)/(1-t)^7*x^4/4! + ....

The coefficients of the numerator polynomials are listed in A008517,
the triangle of second-order Eulerian numbers.

3) F(x) = log(1+x) - x. D(x,t) = x - t*(log(1+x)-x).

The function exp(t*F(x)) is the e.g.f. for A008306, the triangle of
associated Stirling numbers of the first kind. By proposition 1, the
e.g.f. for the diagonals of A008306 is equal to

	D(x,t)^(-1) = x – t*x^2/2! + (2*t+3*t^2)x^3/3!
	
		    - (6*t+20*t^2+15*t^3)*x^4/4! + ....

The coefficient polynomials in t are the row polynomials of A111999.

4) F(x) = exp(x)-1-x. D(x,t) = x-t*(exp(x)-1-x).

The function exp(t*F(x)) is the e.g.f. for A008299, the triangle of
associated Stirling numbers of the second kind. By proposition 1, the
e.g.f. for the diagonals of A008299 is equal to

	D(x,t)^(-1) = (x-t*(exp(x)-1-x))^(-1) = x + t*x^2/2!
	
		    + (t+3*t^2)*x^3/3! + (t+10*t^2+15*t^3)*x^4/4! + ....

The coefficient polynomials in t are the row polynomials of A134991.

5) F(x) = x/(1-x). D(x,t) = x-t*x/(1-x).

The function exp(t*F(x)) is the e.g.f. for A105278 (triangle of unsigned
Lah numbers). By proposition 1, the e.g.f. for the diagonals of A105278
is equal to

	D(x,t)^(-1) = (x-t*x/(1-x))^(-1)
	
		    = x/(1-t) + 2*t/(1-t)^3*x^2/2!

    + 6*(t+t^2)/(1-t)^5*x^3/3! + 24*(t+3*t^2+t^3)/(1-t)^7*x^4/4! + ....

Note that the numerator polynomials in this expansion are multiples
of the Narayana polynomials of A001263.

Others examples include A108767 (F(x) = x/(1-x^2)) and A173020 (F(x)
 = x/(1-x^3)).

REFERENCES

[1] B Drake, An inversion theorem for labeled trees and some limits
of areas under lattice paths. A dissertation presented to the
Faculty of the Graduate School of Arts and Sciences of Brandeis
University, 2008 – available online at
http://people.brandeis.edu/~gessel/homepage/students/drakethesis.pdf

Peter Bala, Dec 02 2011