login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Please make a donation to keep the OEIS running. We are now in our 56th year. In the past year we added 10000 new sequences and reached almost 9000 citations (which often say "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A101276 Triangle read by rows: T(n,k) is the number of ordered trees having n edges and k branches of length 1. 0
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, 54, 106, 45, 126, 0, 51, 22, 74, 168, 196, 360, 126, 357, 0, 127, 43, 173, 372, 706, 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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,8

COMMENTS

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

LINKS

Table of n, a(n) for n=0..77.

Emeric Deutsch, Ordered trees with prescribed root degrees, node degrees and branch lengths, Discrete Math., 282, 2004, 89-94.

J. Riordan, Enumeration of plane trees by branches and endpoints, J. Comb. Theory (A) 19, 1975, 214-222.

FORMULA

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.

EXAMPLE

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.

MAPLE

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

MATHEMATICA

m = 12; G[_] = 0;

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}];

CoefficientList[#, t]& /@ CoefficientList[G[z], z] // Flatten (* Jean-Fran├žois Alcover, Nov 15 2019 *)

CROSSREFS

Cf. A000108, A000106, A026418.

Sequence in context: A291308 A207944 A063088 * A103863 A166395 A061199

Adjacent sequences:  A101273 A101274 A101275 * A101277 A101278 A101279

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Dec 20 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 1 20:34 EST 2020. Contains 338854 sequences. (Running on oeis4.)