login
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

%I #56 May 13 2024 09:15:33

%S 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,

%T 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,

%U 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

%N 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.

%C 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.

%C See related triangle A227543.

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

%C The maximum in each row of the triangle is A274291. - _Torsten Muetze_, Nov 28 2018

%C 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

%H Seiichi Manyama, <a href="/A138158/b138158.txt">Rows n = 0..38, flattened</a>

%H Ron M. Adin and Yuval Roichman, <a href="http://arxiv.org/abs/1201.4669">On maximal chains in the non-crossing partition lattice</a>, arXiv:1201.4669 [math.CO], 2012-2013.

%H Luca Ferrari, <a href="http://arxiv.org/abs/1207.7295">Unimodality and Dyck paths</a>, arXiv:1207.7295 [math.CO], 2012.

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000005">The bounce statistic of a Dyck path</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000006">The dinv statistic of a Dyck path</a>, <a href="http://www.findstat.org/StatisticsDatabase/St000012">The area of a Dyck path</a>.

%H Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/AnaCombi/anacombi.html">Analytic Combinatorics</a>, Cambridge Univ. Press, 2009, page 185.

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

%F 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).

%F Row sums are the Catalan numbers (A000108).

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

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

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

%F 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

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

%e Triangle starts

%e 1,

%e 0, 1,

%e 0, 0, 1, 1,

%e 0, 0, 0, 1, 2, 1, 1,

%e 0, 0, 0, 0, 1, 3, 3, 3, 2, 1, 1,

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

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

%e 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,

%e ... [_Joerg Arndt_, Feb 21 2014]

%p 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

%t nmax = 7;

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

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

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

%t Table[T[n, k], {n, 0, nmax}, {k, 0, n(n+1)/2}] // Flatten (* _Jean-François Alcover_, Jul 11 2018, from Maple *)

%t 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}] /.

%t sol, {2}] // Grid (* _Geoffrey Critzer_, Jul 14 2020 *)

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

%K nonn,tabf

%O 0,12

%A _Emeric Deutsch_, Mar 21 2008