OFFSET
1,3
COMMENTS
An increasing tree is a labeled rooted tree with the property that the sequence of labels along any path starting from the root is increasing. A000111(n) for n >= 0 enumerates increasing unordered trees on the vertex set {1,2,...,n}, rooted at 1, in which all outdegrees are <= 2 (plane unary binary trees in the notation of [Bergeron et al.]).
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, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
FORMULA
TABLE ENTRIES
(1)... T(n,k) = k!*A147315(n-1,k-1).
(2)... T(n,k) = Sum_{j = 0..k} (-1)^(k-j)*binomial(k,j)*Z(n,j), where Z(n,x) denotes the zigzag polynomials as described in A147309.
Recurrence relation
(3)... T(n+1,k) = k*{T(n,k-1)+T(n,k)+1/2*T(n,k+1)}.
GENERATING FUNCTION
Let E(t) = sec(t)+tan(t)-1. E(t) is the egf for the enumeration of increasing unordered trees on the vertex set {1,2,...,n}, rooted at 1, in which all outdegrees are <=2 (plane unary binary trees in the notation of [Bergeron et al.]).
The egf of the present array is
(4)... 1/(1-x*E(t)) - 1 = Sum_{n >= 1} R(n,x)*t^n/n! = x*t + x*(1+2*x)*t^2/2! + x*(2+6*x+6*x^2)*t^3/3! + ...
ROW POLYNOMIALS
The row generating polynomials R(n,x) begin.
... R(1,x) = x
... R(2,x) = x*(1+2*x)
... R(3,x) = x*(2+6*x+6*x^2)
... R(4,x) = x*(5+22*x+36*x^2+24*x^3).
The ordered Bell polynomials OB(n,x) are the row polynomials of A019538 given by the formula
(5)... OB(n,x) = Sum_{k = 1..n} k!*Stirling2(n,k)*x^k.
By comparing the e.g.f.s for A019538 and the present table we obtain the surprising identity
(6)... (-i)^(n-1)*OB(n,x)/x = R(n,y)/y, where i = sqrt(-1) and x = i*y + (-1/2+i/2). It follows that the zeros of the polynomial R(n,y)/y lie on the vertical line Re(y) = -1/2 in the complex plane.
RELATIONS WITH OTHER SEQUENCES
(7)... T(n,1) = A000111(n).
Setting y = 0 in (6) yields
(8)... A000111(n) = i^(n+1)*Sum_{k=1..n} (-1)^k*k!*Stirling2(n,k) *((1+i)/2)^(k-1).
EXAMPLE
Triangle begins
n\k|....1......2......3......4......5......6......7
===================================================
..1|....1
..2|....1......2
..3|....2......6......6
..4|....5.....22.....36.....24
..5|...16.....90....210....240....120
..6|...61....422...1260...2040...1800....720
..7|..272...2226...8106..16800..21000..15120...5040
..
Examples of recurrence relation for table entries:
T(5,2) = 2*{T(4,1)+T(4,2)+1/2*T(4,3)} = 2*(5+22+18) = 90;
T(6,1) = 1*{T(5,0)+T(5,1)+1/2*T(5,2)} = 16 + 1/2*90 = 61.
Examples of forests:
T(4,2) = 22. The 11 unordered forests consisting of 2 trees on 4 nodes are shown in the example section of A147315. Putting an order on the trees in a forest produces 2!*11 = 22 ordered forests.
MAPLE
#A185421 E := t -> sec(t)+tan(t)-1:
F := (x, t) -> 1/(1-x*E(t)) - 1:
Fser := series(F(x, t), t=0, 12):
for n from 1 to 7 do
seq(coeff(n!*coeff(Fser, t, n), x, i), i=1..n) od;
MATHEMATICA
nmax = 9; t[n_ /; n > 0, k_ /; k > 0] := t[n, k] = k*(t[n-1, k-1] + t[n-1, k] + 1/2*t[n-1, k+1]);
t[1, 1] = 1; t[0, _] = 0; t[_, 0] = 0; Flatten[Table[t[n, k], {n, 1, nmax}, {k, 1, n}]]
(* Jean-François Alcover, Jun 22 2011, after recurrence *)
PROG
(PARI) {T(n, k)=if(n<1||k<1||k>n, 0, if(n==1, 1, k*(T(n-1, k-1)+T(n-1, k)+T(n-1, k+1)/2)))}
(PARI) {T(n, k)=local(X=x+x*O(x^n)); n!*polcoeff(polcoeff(1/(1-y*((1+sin(X))/cos(X)-1))-1, n, x), k, y)}
CROSSREFS
KEYWORD
AUTHOR
Peter Bala, Jan 31 2011
EXTENSIONS
Maple program corrected by Peter Luschny, Aug 02 2011
STATUS
approved