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.

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

Offset: 0

Author

Emeric Deutsch, Mar 21 2008

Keywords

• nonn
• tabf

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

Examples

			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]
		

Links

• Seiichi Manyama, Rows n = 0..38, flattened
• Ron M. Adin and Yuval Roichman, On maximal chains in the non-crossing partition lattice, arXiv:1201.4669 [math.CO], 2012-2013.
• 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.
• Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge Univ. Press, 2009, page 185.

Crossrefs

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

Programs

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 *)

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