|
%I #8 Dec 28 2016 17:40:48
%S 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,
%T 836,1940,1557,484,45,2377,6142,5690,2247,331,9,6869,19454,20535,9792,
%U 2010,126,20042,61893,73123,40997,10820,1116,21,59071,197280,258220
%N 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)).
%C Row n has 1+floor(n/2) terms.
%C Row sums are the Catalan numbers (A000108).
%C T(2n,n) = A001006(n-1) for n>=1 (the Motzkin numbers).
%C T(2n+1,n) = A005717(n+1) for n>=0.
%H Emeric Deutsch, <a href="http://dx.doi.org/10.1016/j.disc.2003.10.021">Ordered trees with prescribed root degrees, node degrees and branch lengths</a>, Discrete Math., 282, 2004, 89-94.
%H J. Riordan, <a href="http://dx.doi.org/10.1016/S0097-3165(75)80010-0">Enumeration of plane trees by branches and endpoints</a>, J. Comb. Theory (A) 19, 1975, 214-222.
%F G.f. G = G(t,z) satisfies z(1+tz)G^2-(1+z-z^2+tz^2)G+1+z-z^2+tz^2=0.
%e 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.
%e Triangle starts:
%e 1;
%e 1;
%e 1, 1;
%e 3, 2;
%e 6, 7, 1;
%e 16, 20, 6;
%p G:=1/2/(t*z^2+z)*(-z^2+z+1+t*z^2-sqrt(-5*z^2-6*t*z^3-2*z+2*z^3-3*t^2*z^4-2*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;
%Y Cf. A000108, A001006, A005717, A102003.
%K nonn,tabf
%O 0,5
%A _Emeric Deutsch_, Dec 25 2004
|
