OFFSET
1,4
COMMENTS
Define a sequence of polynomials P(n,x) by means of the recurrence
relation
(1)... P(n+1,x) = x*{P(n,x-1)-P(n,x)+P(n,x+1)}
with starting value P(0,x) = 1. The first few polynomials are
P(1,x) = x
P(2,x) = x^2
P(3,x) = x*(x^2+2),
P(4,x) = x^2*(x^2+8),
P(5,x) = x*(x^4+20*x^2+18).
This triangle lists the coefficients of these polynomials in
ascending powers of x. The triangle has links with A080635, which
gives the number of ordered increasing 0-1-2 trees on n nodes (plane
unary-binary trees in the notation of [BERGERON et al.]). The number of
forests of k such trees on n nodes is given by the formula
... 1/k!*sum {j = 0..k} (-1)^(k-j)*binomial(k,j)*P(n,j).
See A185422.
We also have A080635(n) = P(n,1), which can be used to calculate the terms of A080635 - see A185416.
REFERENCES
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, in Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1922, pp. 24-48.
LINKS
G. C. Greubel, Table of n, a(n) for the first 50 rows, flattened
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of increasing trees
FORMULA
GENERATING FUNCTION
The e.g.f. is
(1)... F(x, t) = E(t)^x = Sum_{n >= 0} P(n, x) * t^n/n!,
where
E(t) = 1/2+sqrt(3)/2*tan[sqrt(3)/2*t+Pi/6] = 1 + t + t^2/2! + 3*t^3/3! + 9*t^4/4! + ... is the e.g.f. for A080635.
ROW POLYNOMIALS
One easily checks that
... d/dt(F(x,t)) = x*(F(x-1,t)-F(x,t)+F(x+1,t))
and hence the row generating polynomials P(n,x) satisfy the recurrence
relation
(2)... P(n+1,x) = x*{P(n,x-1)-P(n,x)+P(n,x+1)}.
RELATIONS WITH OTHER SEQUENCES
A080635(n) = P(n,1).
A185422(n,k) = 1/k!*Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*P(n,j).
A185423(n,k) = Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*P(n,j).
EXAMPLE
Example
Triangle begins
n\k|....1......2......3......4......5......6......7......8
==========================================================
..1|....1
..2|....0......1
..3|....2......0......1
..4|....0......8......0......1
..5|...18......0.....20......0......1
..6|....0....148......0.....40......0......1..
..7|..378......0....658......0.....70......0......1
..8|....0...5040......0...2128......0....112......0......1
..
MAPLE
P := proc(n, x)
description 'polynomial sequence P(n, x)'
if n = 0
return 1
else return
x*(P(n-1, x-1)-P(n-1, x)+P(n-1, x+1))
end proc:
with(PolynomialTools):
for n from 1 to 10
CoefficientList(P(n, x), x);
end do;
MATHEMATICA
p[0][x_] = 1; p[n_][x_] := p[n][x] = x*(p[n-1][x-1] - p[n-1][x] + p[n-1][x+1]) // Expand; row[n_] := CoefficientList[ p[n][x], x]; Table[row[n] // Rest, {n, 1, 10}] // Flatten (* Jean-François Alcover, Sep 11 2012 *)
CROSSREFS
KEYWORD
AUTHOR
Peter Bala, Jan 27 2011
STATUS
approved