|
| |
|
|
A094503
|
|
Triangle read by rows: coefficients d(n,k) of Andre polynomials D(x,n) = Sum_{k>0} d(n,k)*x^k.
|
|
5
|
|
|
|
1, 1, 1, 1, 1, 4, 1, 11, 4, 1, 26, 34, 1, 57, 180, 34, 1, 120, 768, 496, 1, 247, 2904, 4288, 496, 1, 502, 10194, 28768, 11056, 1, 1013, 34096, 166042, 141584, 11056, 1, 2036, 110392, 868744, 1372088, 349504, 1, 4083, 349500, 4247720, 11204160, 6213288
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,6
|
|
|
COMMENTS
|
a(n,k) is the number of increasing 0-1-2 trees on [n] with k leaves. An increasing 0-1-2 tree on [n] is an unordered tree on [n], rooted at 1, in which each vertex has <= 2 children and the labels increase along each path from the root. Example: a(4,2)=4 counts the trees with edges as follows, {1->2->3,1->4}, {1->2->4,1->3}, {1->2->4,2->3}, {1->3->4,1->2}. - David Callan, Oct 24 2004
|
|
|
LINKS
|
F. Bergeron, Ph. Flajolet, and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
|
|
|
FORMULA
|
D(1, n) = A000111(n), Euler or up/down numbers. D(1/2, n) = A000142(n)*(1/2)^n. D(1/4, n) = A080795(n)*(1/4)^n.
Recurrence equation: T(n,k) = k*T(n-1,k) + (n+2-2*k)*T(n-1,k-1) for n >= 1 and 1 <= k <= floor((n+1)/2).
Let r(t) = sqrt(1-2*t) and w(t) = (1-r(t))/(1+r(t)). The e.g.f. is F(t,z) = r(t)*(1 + w(t)*exp(r(t)*z))/(1 - w(t)*exp(r(t)*z)) = 1 + t*z + t*z^2/2! + (t+t^2)*z^3/3! + (t+4*t^2)*z^4/4! + ... (Foata and Han, 2001, section 7).
Note that (F(2*t,z) - 1)/(2*t) is the e.g.f. for A101280.
The modified e.g.f. A(t,z) := (F(t,z) - 1)/t = z + z^2/2! + (1+t)*z^3/3! + (1+4*t)*z^4/4! + ... satisfies the autonomous partial differential equation dA/dz = 1 + A + 1/2*t*A^2 with A(t,0) = 1. It follows that the inverse function A(t,z)^(-1) may be expressed as an integral: A(t,z)^(-1) = Integral_{x = 0..z} 1/(1+x+1/2*t*x^2) dx.
Applying [Dominici, Theorem 4.1] to invert the integral gives the following method for calculating the row polynomials R(n,t) of the table: let f(t,x) = 1+x+1/2*t*x^2 and let D be the operator f(t,x)*d/dx. Then R(n+1,t) = t*D^n(f(t,x)) evaluated at x = 0.
By Bergeron et al., Theorem 1, the shifted row polynomial 1/t*R(n,t) is the generating function for rooted non-plane increasing 0-1-2 trees on n vertices, where the vertices of outdegree 2 have weight t and all other vertices have weight 1. An example is given below.
1/(2*t)*(1+t)^(n+1)*R(n,2*t/(1+t)^2) = the n-th Eulerian polynomial of A008292. For example, n = 5 gives 1/(2*t)*(1+t)^6*R(5,2*t/(1+t)^2) = 1 + 26*t + 66*t^2 + 26*t^3 + t^4.
(End)
There is a second family of polynomials which also matches the data and is different from the André polynomials as defined by Foata and Han (2001), formula 3.5. Let u = sqrt(s^2-2) and F(s,x) = u*x-2*log((exp(u*x)*(1-s/u)+s/u+1)/2), then for n>=0 the sequence of polynomials p_{n}(s) = (n+2)!*[x^(n+2)]F(s,x) starts 1, s, s^2+1, s^3+4*s, s^4+11*s^2+4, s^5+26*s^3+34*s, s^6+57*s^4+180*s^2+34, ... and the nonzero coefficients of these polynomials in descending order coincide with the sequence a(n). p_{n}(0) is an aerated version of the reduced tangent numbers, p_{2*n}(0) = A002105(n+1) for n>=0. In contrast, the André polynomials vanish at t=0 except for n=0. - Peter Luschny, Jul 01 2012
|
|
|
EXAMPLE
|
Triangle begins:
1
1
1 1
1 4
1 11 4
1 26 34
1 57 180 34
...
Recurrence equation: T(6,3) = 3*T(5,3) + 2*T(5,2) = 3*4 + 2*11 = 34.
n = 4: the 5 weighted non-plane increasing 0-1-2 trees on 4 vertices are
.........................................................
..4......................................................
..|......................................................
..3............4............4.............3.......3...4..
..|.........../............/............./.........\./...
..2......2...3........3...2.........4...2........(t)2....
..|.......\./..........\./...........\./............|....
..1.....(t)1.........(t)1..........(t)1.............1....
.........................................................
Hence row polynomial R(4,t) = (1 + 4*t)*t.
(End)
|
|
|
MAPLE
|
A094503:=proc(n, k) options remember: if(n=1 and k=1) then RETURN(1) elif(1<=k and k<=floor((n+1)/2) and n>=1) then RETURN(k*A094503(n-1, k)+(n+2-2*k)*A094503(n-1, k-1)) else RETURN(0) fi: end; seq(seq(A094503(n, k), k=1..floor((n+1)/2)), n=1..14);
|
|
|
MATHEMATICA
|
t[1, 1] = 1; t[n_, k_] /; Not[1 <= k <= (n+1)/2] = 0; t[n_, k_] := t[n, k] = k*t[n-1, k] + (n+2-2*k)*t[n-1, k-1]; Table[t[n, k], {n, 0, 13}, {k, 1, (n + 1)/2}] // Flatten (* Jean-François Alcover, Nov 22 2012, after Maple *)
|
|
|
PROG
|
(Sage)
def p(n) :
s = var('s'); u = sqrt(s^2-2)
egf = u*x-2*ln((exp(u*x)*(1-s/u)+s/u+1)/2)
return factorial(n+2)*egf.series(x, n+4).coefficient(x, n+2)
def A094503_row(n) : return [p(n).coefficient(s, n-2*i) for i in (0..n//2)]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
