login
The OEIS is supported by the many generous donors to the OEIS 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
It appears that for j = 0,1,...,n-1 the first j terms of the rows in reversed order are given by A000041(j), the partition numbers. - Geoffrey Critzer, Jul 14 2020
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.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 185.
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 *)
nn = 10; f[z_, u_] := Sum[Sum[a[n, k] u^k z^n, {k, 0, Binomial[n, 2]}], {n, 1, nn}]; sol = SolveAlways[Series[0 == f[z, u] - z/(1 - f[u z, u]) , {z, 0, nn}], {z, u}]; Level[Table[Table[a[n, k], {k, 0, Binomial[n, 2]}], {n, 1, nn}] /.
sol, {2}] // Grid (* Geoffrey Critzer, Jul 14 2020 *)
CROSSREFS
Sequence in context: A064663 A025923 A351358 * A057276 A259829 A035185
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 | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 21 12:33 EST 2024. Contains 370235 sequences. (Running on oeis4.)