cp's OEIS Frontend

A101276 Triangle read by rows: T(n,k) is the number of ordered trees having n edges and k branches of length 1.

%I A101276 #16 Jul 22 2024 04:38:03
%S A101276 1,0,1,1,0,1,1,2,0,2,2,2,6,0,4,3,8,6,16,0,9,6,14,30,16,45,0,21,11,36,
%T A101276 54,106,45,126,0,51,22,74,168,196,360,126,357,0,127,43,173,372,706,
%U A101276 675,1197,357,1016,0,323,87,378,981,1636,2775,2268,3913,1016,2907,0,835,176,860,2310,4771,6660,10451,7469,12644,2907,8350,0,2188
%N A101276 Triangle read by rows: T(n,k) is the number of ordered trees having n edges and k branches of length 1.
%C A101276 Row n has n+1 terms (n>=0). Row sums are the Catalan numbers (A000108). Column 0 yields A026418. T(n,n)=A001006(n-1) (n>0) (the Motzkin numbers).
%H A101276 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 A101276 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 A101276 G.f.: G=G(t, z) satisfies z(t+z-tz)G^2-(1-z+tz+z^2-tz^2)G+1-z+tz+z^2-tz^2=0.
%e A101276 T(3,1)=2 because we have the tree with three edges hanging from the root and the tree with one edge hanging from the root at the end of which two edges are hanging.
%p A101276 G := 1/2/(-z^2+t*z^2-t*z)*(-1+z-t*z-z^2+t*z^2+sqrt(1-3*t^2*z^2-8*t*z^3+6*t^2*z^3+6*z^4*t-3*t^2*z^4-2*t*z-z^2-3*z^4+2*z^3-2*z+4*t*z^2)): Gser:=simplify(series(G,z=0,13)): P[0]:=1: for n from 1 to 11 do P[n]:=coeff(Gser,z^n) od: for n from 0 to 11 do seq(coeff(t*P[n],t^k),k=1..n+1) od; # yields the sequence in triangular form
%t A101276 m = 12; G[_] = 0;
%t A101276 Do[G[z_] = (1 + t z - t z^2 - z + z^2 + G[z]^2 (t z - t z^2 + z^2))/(1 + t z - t z^2 - z + z^2) + O[z]^m, {m}];
%t A101276 CoefficientList[#, t]& /@ CoefficientList[G[z], z] // Flatten (* _Jean-François Alcover_, Nov 15 2019 *)
%Y A101276 Cf. A000108, A001006, A026418.
%K A101276 nonn,tabl
%O A101276 0,8
%A A101276 _Emeric Deutsch_, Dec 20 2004