

A102004


Triangle read by rows: T(n,k) is the number of ordered trees with n edges and having k branches of even length (n>=0, 0<=k<=floor(n/2)).


1



1, 1, 1, 1, 3, 2, 6, 7, 1, 16, 20, 6, 40, 64, 26, 2, 109, 196, 108, 16, 297, 619, 414, 96, 4, 836, 1940, 1557, 484, 45, 2377, 6142, 5690, 2247, 331, 9, 6869, 19454, 20535, 9792, 2010, 126, 20042, 61893, 73123, 40997, 10820, 1116, 21, 59071, 197280, 258220
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,5


COMMENTS

Row n has 1+floor(n/2) terms.
Row sums are the Catalan numbers (A000108).
T(2n,n) = A001006(n1) for n>=1 (the Motzkin numbers).
T(2n+1,n) = A005717(n+1) for n>=0.


LINKS

Table of n, a(n) for n=0..51.
Emeric Deutsch, Ordered trees with prescribed root degrees, node degrees and branch lengths, Discrete Math., 282, 2004, 8994.
J. Riordan, Enumeration of plane trees by branches and endpoints, J. Comb. Theory (A) 19, 1975, 214222.


FORMULA

G.f. G = G(t,z) satisfies z(1+tz)G^2(1+zz^2+tz^2)G+1+zz^2+tz^2=0.


EXAMPLE

T(3,0)=3 because we have: (i) tree with 3 edges hanging from the root, (ii) tree with one edge hanging from the root, at the end of which 2 edges are hanging and (iii) tree with a path of length 3 hanging from the root.
Triangle starts:
1;
1;
1, 1;
3, 2;
6, 7, 1;
16, 20, 6;


MAPLE

G:=1/2/(t*z^2+z)*(z^2+z+1+t*z^2sqrt(5*z^26*t*z^32*z+2*z^33*t^2*z^42*t*z^2+2*t*z^4+1+z^4)): Gserz:=simplify(series(G, z=0, 16)): P[0]:=1: for n from 1 to 14 do P[n]:=sort(expand(coeff(Gserz, z^n))) od:for n from 0 to 14 do seq(coeff(t*P[n], t^k), k=1..1+floor(n/2)) od;


CROSSREFS

Cf. A000108, A001006, A005717, A102003.
Sequence in context: A283479 A087237 A275630 * A233208 A196518 A207636
Adjacent sequences: A102001 A102002 A102003 * A102005 A102006 A102007


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Dec 25 2004


STATUS

approved



