OFFSET
0,6
COMMENTS
A pyramid in a Dyck word (path) is a factor of the form u^h d^h, h being the height of the pyramid. A pyramid in a Dyck word w is maximal if, as a factor in w, it is not immediately preceded by a u and immediately followed by a d. The pyramid weight of a Dyck path (word) is the sum of the heights of its maximal pyramids.
Triangle T(n,k), 0 <= k <= n, read by rows, given by [0, 0, 1, 0, 0, 1, 0, 0, 1, ...] (periodic sequence 0,0,1) DELTA [1, 1, 0, 1, 1, 0, 1, 1, 0, ...] (periodic sequence 1,1,0), where DELTA is the operator defined in A084938. - Philippe Deléham, Aug 18 2006
Peter Luschny observes that one of the rows of this triangle seems to appear on page 26 of Knuth (2014). - N. J. A. Sloane, Aug 02 2014
LINKS
Alois P. Heinz, Rows n = 0..140, flattened
Xiaomei Chen, Yuan Xiang, Counting generalized Schröder paths, arXiv:2009.04900 [math.CO], 2020.
A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176.
D. E. Knuth, Problems That Philippe Would Have Loved, Paris 2014.
FORMULA
G.f.: G = G(t, z) satisfies z(1-tz)G^2-(1+z-2tz)G+1-tz = 0.
Sum_{k=0..n} T(n,k) = A000108(n). - Philippe Deléham, Aug 18 2006
EXAMPLE
T(4,3)=5 because the Dyck paths of semilength 4 having pyramid weight 3 are: (ud)u(ud)(ud)d, u(ud)(ud)d(ud), u(ud)(ud)(ud)d, u(ud)(uudd)d and u(uudd)(ud)d [here u=(1,1), d=(1,-1) and the maximal pyramids, of total length 3, are shown between parentheses].
Triangle begins:
1;
0, 1;
0, 0, 2;
0, 0, 1, 4;
0, 0, 1, 5, 8;
0, 0, 1, 7, 18, 16;
0, 0, 1, 9, 34, 56, 32;
0, 0, 1, 11, 55, 138, 160, 64;
0, 0, 1, 13, 81, 275, 500, 432, 128;
...
MATHEMATICA
nmax=11;
DELTA[r_, s_] := Module[{m=Min[Length[r], Length[s]], p, q, t, x, y}, q[k_] := x*r[[k+1]] + y*s[[k+1]]; p[0, _] = 1; p[_, -1] = 0; p[n_ /; n >= 1, k_ /; k >= 0] := p[n, k] = p[n, k-1] + q[k]*p[n-1, k+1] // Expand; t[n_, k_] := Coefficient[p[n, 0], x^(n-k)*y^k]; t[0, 0] = p[0, 0]; Table[ t[n, k], {n, 0, m}, {k, 0, n}]];
Table[Mod[1+2n^2, 3], {n, nmax}] ~DELTA~ Table[1-Mod[1+2n^2, 3], {n, nmax}] (* Jean-François Alcover, Jun 06 2019 *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Mar 10 2004
STATUS
approved