

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.
Row n contains 1+n(n+1)/2 terms.
It appears that for j = 0,1,...,n1 the first j terms of the rows in reversed order are given by A000041(j), the partition numbers.  Geoffrey Critzer, Jul 14 2020


LINKS



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[nj1]*t^(n1j), j=0..n1 ) (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(n1).
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,


MAPLE

P[0]:=1: for n to 7 do P[n]:=sort(expand(t*(sum(P[j]*P[nj1]*t^(nj1), j= 0.. n1)))) 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[nj1]*t^(nj1), {j, 0, n1}];
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 (* JeanFranç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}] /.


CROSSREFS



KEYWORD

nonn,tabf


AUTHOR



STATUS

approved



