

A185421


Ordered forests of k increasing unordered trees on the vertex set {1,2,...,n} in which all outdegrees are <= 2.


6



1, 1, 2, 2, 6, 6, 5, 22, 36, 24, 16, 90, 210, 240, 120, 61, 422, 1260, 2040, 1800, 720, 272, 2226, 8106, 16800, 21000, 15120, 5040, 1385, 13102, 56196, 141624, 226800, 231840, 141120, 40320, 7936, 85170, 420330, 1244880, 2421720, 3175200, 2751840, 1451520, 362880
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

An increasing tree is a labelled 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.]).
The entry T(n,k) of the present table counts ordered forests of k such trees having n nodes in total. See below for an example. For unordered forests see A147315. For a table of ordered forests of increasing ordered trees in which all outdegrees are <=2 see A185423.


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. 2448.


FORMULA

TABLE ENTRIES
(1)... T(n,k) = k!*A147315(n1,k1).
(2)... T(n,k) = Sum_{j = 0..k} (1)^(kj)*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,k1)+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/(1x*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 egf's for A019538 and the present table we obtain the surprising identity
(6)... (i)^(n1)*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)^(k1).


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/(1x*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[n1, k1] + t[n1, k] + 1/2*t[n1, k+1]);
t[1, 1] = 1; t[0, _] = 0; t[_, 0] = 0; Flatten[Table[t[n, k], {n, 1, nmax}, {k, 1, n}]]
(* JeanFrançois Alcover, Jun 22 2011, after recurrence *)


PROG

(PARI) {T(n, k)=if(n<1k<1k>n, 0, if(n==1, 1, k*(T(n1, k1)+T(n1, k)+T(n1, k+1)/2)))}
(PARI) {T(n, k)=local(X=x+x*O(x^n)); n!*polcoeff(polcoeff(1/(1y*((1+sin(X))/cos(X)1))1, n, x), k, y)}


CROSSREFS

Cf. A147315, A147309, A185423.
Sequence in context: A173869 A247377 A167909 * A219976 A063944 A086447
Adjacent sequences: A185418 A185419 A185420 * A185422 A185423 A185424


KEYWORD

nonn,easy,tabl


AUTHOR

Peter Bala, Jan 31 2011


EXTENSIONS

Maple program corrected by Peter Luschny, Aug 02 2011


STATUS

approved



