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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A138157 Triangle read by rows: T(n,k) is the number of binary trees with n edges and path length k; 0<=k<=n(n+1)/2. 4
1, 0, 2, 0, 0, 1, 4, 0, 0, 0, 0, 4, 2, 8, 0, 0, 0, 0, 0, 0, 6, 8, 8, 4, 16, 0, 0, 0, 0, 0, 0, 0, 0, 4, 24, 4, 28, 16, 16, 8, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 24, 36, 48, 24, 56, 40, 56, 32, 32, 16, 64, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 60, 72, 144, 26, 168, 104, 128, 64, 176, 80, 112 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Row n has 1+n(n+1)/2 terms.

Row sums are the Catalan numbers (A000108).

Column sums yield A095830.

Sum(k*T(n,k),k>=0)=A138156(n).

The g.f. B(w,z) in the Knuth reference is related to the above G(t,z) through B(t,z)=1+zG(t,z).

REFERENCES

D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, 1997, Vol. 1, p. 405 (exercise 5) and p. 595 (solution).

LINKS

Alois P. Heinz, Rows n = 0..50, flattened

Marilena Barnabei, Flavio Bonetti, and Niccolò Castronuovo, Motzkin and Catalan Tunnel Polynomials, J. Int. Seq., Vol. 21 (2018), Article 18.8.8.

FORMULA

G.f.=G(t,z) satisfies G(t,z)=1 + 2tzG(t,tz) + [tzG(t,tz)]^2. The row generating polynomials P[n]=P[n](t) (n=1,2,...) are given by P[n]=t^n (2P[n-1] + sum(P[i]P[n-2-i], i=0..n-2); P[0]=1.

EXAMPLE

T(2,3)=4 because we have the path trees LL, LR. RL and RR, where L (R) denotes a left (right) edge; each of these four trees has path length 3.

Triangle starts:

1;

0,2;

0,0,1,4;

0,0,0,0,4,2,8;

0,0,0,0,0,0,6,8,8,4,16;

0,0,0,0,0,0,0,0,4,24,4,28,16,16,8,32;

MAPLE

P[0]:=1: for n to 7 do P[n]:=sort(expand(t^n*(2*P[n-1]+add(P[i]*P[n-2-i], i= 0..n-2)))) end do: for n from 0 to 7 do seq(coeff(P[n], t, j), j=0..(1/2)*n*(n+1)) end do; # yields sequence in triangular form

MATHEMATICA

p[n_] := p[n] = t^n*(2p[n-1] + Sum[p[i]*p[n-2-i], {i, 0, n-2}]); p[0] = 1; Flatten[ Table[ CoefficientList[ p[n], t], {n, 0, 7}]] (* Jean-François Alcover, Jul 22 2011, after Maple prog. *)

CROSSREFS

Cf. A000108, A095830, A138156.

Sequence in context: A273185 A259784 A145224 * A342243 A073429 A123634

Adjacent sequences:  A138154 A138155 A138156 * A138158 A138159 A138160

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Mar 20 2008

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 June 21 06:03 EDT 2021. Contains 345355 sequences. (Running on oeis4.)