login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A120988 Triangle read by rows: T(n,k) is the number of binary trees with n edges and such that the first leaf in the preorder traversal is at level k (1<=k<=n). A binary tree is a rooted tree in which each vertex has at most two children and each child of a vertex is designated as its left or right child. 1
2, 1, 4, 2, 4, 8, 5, 9, 12, 16, 14, 24, 30, 32, 32, 42, 70, 85, 88, 80, 64, 132, 216, 258, 264, 240, 192, 128, 429, 693, 819, 833, 760, 624, 448, 256, 1430, 2288, 2684, 2720, 2490, 2080, 1568, 1024, 512, 4862, 7722, 9009, 9108, 8361, 7068, 5488, 3840, 2304, 1024 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,1

COMMENTS

Row sums are the Catalan numbers (A000108). T(n,1)=A000108(n-1) for n>=2 (the Catalan numbers). T(n,n)=2^n. Sum(k*T(n,k),k=1..n)=A120989(n).

LINKS

Table of n, a(n) for n=1..55.

FORMULA

T(n,k)=Sum(j*binomial(k,j)*binomial(2n-2k+j,n-k)/(2n-2k+j), j=0..k). G.f.=1/[1-tz(1+C)], where C=[1-sqrt(1-4z)]/(2z) is the Catalan function.

EXAMPLE

T(2,1)=1 because we have the tree /\.

Triangle starts:

2;

1;4;

2,4,8;

5,9,12,16;

14,24,30,32,32;

MAPLE

T:=proc(n, k) if k<n then add(j*binomial(k, j)*binomial(2*n-2*k+j, n-k)/(2*n-2*k+j), j=0..k) elif k=n then 2^n else 0 fi end:for n from 1 to 11 do seq(T(n, k), k=1..n) od; # yields sequence in triangular form

CROSSREFS

Cf. A000108, A120989, A121445.

Sequence in context: A105474 A216568 A219432 * A095979 A276133 A054269

Adjacent sequences:  A120985 A120986 A120987 * A120989 A120990 A120991

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Jul 30 2006

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified January 19 21:35 EST 2018. Contains 297938 sequences.