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!)
A138158 Triangle read by rows: T(n,k) is the number of ordered trees with n edges and path length k; 0 <= k <= n(n+1)/2. 7
1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 2, 1, 1, 0, 0, 0, 0, 1, 3, 3, 3, 2, 1, 1, 0, 0, 0, 0, 0, 1, 4, 6, 7, 7, 5, 5, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 1, 5, 10, 14, 17, 16, 16, 14, 11, 9, 7, 5, 3, 2, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 6, 15, 25, 35, 40, 43, 44, 40, 37, 32, 28, 22, 18, 13, 11, 7, 5, 3, 2, 1, 1 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,12

COMMENTS

T(n,k) is the number of Dyck paths of semilength n for which the sum of the heights of the vertices that terminate an upstep (i.e. peaks and doublerises) is k. Example: T(4,7)=3 because we have UUDUDUDD, UDUUUDDD and UUUDDDUD.

See related triangle A227543.

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

The maximum in each row of the triangle is A274291. - Torsten Muetze, Nov 28 2018

LINKS

Seiichi Manyama, Rows n = 0..38, flattened

Ron M. Adin, Yuval Roichman, On maximal chains in the non-crossing partition lattice, arXiv:1201.4669 [math.CO], 2012.

Luca Ferrari, Unimodality and Dyck paths, arXiv:1207.7295 [math.CO], 2012.

FindStat - Combinatorial Statistic Finder, The bounce statistic of a Dyck path, The dinv statistic of a Dyck path, The area of a Dyck path.

FORMULA

G.f. G(t,z) satisfies G(t,z) = 1+t*z*G(t,z)*G(t,t*z).

Row generating polynomials P[n]=P[n](t) are given by P[0]=1, P[n] = t * Sum( P[j]*P[n-j-1]*t^(n-1-j), j=0..n-1 ) (n>=1).

Row sums are the Catalan numbers (A000108).

Sum of entries in column n = A005169(n).

Sum_{k=0..n(n+1)/2} k*T(n,k) = A000346(n-1).

T(n,k) = A047998(k,n).

G.f.: 1/(1 - x*y/(1 - x*y^2/(1 - x*y^3/(1 - x*y^4/(1 - x*y^5)/(1 - ... ))))), a continued fraction. - Ilya Gutkovskiy, Apr 21 2017

EXAMPLE

T(2,2)=1 because /\ is the only ordered tree with 2 edges and path length 2.

Triangle starts

1,

0, 1,

0, 0, 1, 1,

0, 0, 0, 1, 2, 1, 1,

0, 0, 0, 0, 1, 3, 3, 3, 2, 1, 1,

0, 0, 0, 0, 0, 1, 4, 6, 7, 7, 5, 5, 3, 2, 1, 1,

0, 0, 0, 0, 0, 0, 1, 5, 10, 14, 17, 16, 16, 14, 11, 9, 7, 5, 3, 2, 1, 1,

0, 0, 0, 0, 0, 0, 0, 1, 6, 15, 25, 35, 40, 43, 44, 40, 37, 32, 28, 22, 18, 13, 11, 7, 5, 3, 2, 1, 1,

... [Joerg Arndt, Feb 21 2014]

MAPLE

P[0]:=1: for n to 7 do P[n]:=sort(expand(t*(sum(P[j]*P[n-j-1]*t^(n-j-1), j= 0.. n-1)))) 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

nmax = 7;

P[0] = 1; P[n_] := P[n] = t*Sum[P[j]*P[n-j-1]*t^(n-j-1), {j, 0, n-1}];

row[n_] := row[n] = CoefficientList[P[n] + O[t]^(n(n+1)/2 + 1), t];

T[n_, k_] := row[n][[k+1]];

Table[T[n, k], {n, 0, nmax}, {k, 0, n(n+1)/2}] // Flatten (* Jean-Fran├žois Alcover, Jul 11 2018, from Maple *)

CROSSREFS

Cf. A227543, A000108, A005169, A000346, A047998, A274291.

Sequence in context: A321923 A064663 A025923 * A057276 A259829 A035185

Adjacent sequences:  A138155 A138156 A138157 * A138159 A138160 A138161

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Mar 21 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 March 28 20:01 EDT 2020. Contains 333103 sequences. (Running on oeis4.)