cp's OEIS Frontend

A091866 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having pyramid weight k.

%I A091866 #32 Dec 09 2020 19:58:22
%S A091866 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,
%T A091866 11,55,138,160,64,0,0,1,13,81,275,500,432,128,0,0,1,15,112,481,1205,
%U A091866 1672,1120,256,0,0,1,17,148,770,2471,4797,5264,2816,512,0,0,1,19,189,1156,4536,11403,17738,15808,6912,1024
%N A091866 Triangle read by rows: T(n,k) is the number of Dyck paths of semilength n having pyramid weight k.
%C A091866 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.
%C A091866 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
%C A091866 _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
%H A091866 Alois P. Heinz, <a href="/A091866/b091866.txt">Rows n = 0..140, flattened</a>
%H A091866 Xiaomei Chen, Yuan Xiang, <a href="https://arxiv.org/abs/2009.04900">Counting generalized Schröder paths</a>, arXiv:2009.04900 [math.CO], 2020.
%H A091866 A. Denise and R. Simion, <a href="http://dx.doi.org/10.1016/0012-365X(93)E0147-V">Two combinatorial statistics on Dyck paths</a>, Discrete Math., 137, 1995, 155-176.
%H A091866 D. E. Knuth, <a href="http://www-cs-faculty.stanford.edu/~uno/flaj2014.pdf">Problems That Philippe Would Have Loved</a>, Paris 2014.
%F A091866 G.f.: G = G(t, z) satisfies z(1-tz)G^2-(1+z-2tz)G+1-tz = 0.
%F A091866 Sum_{k=0..n} T(n,k) = A000108(n). - _Philippe Deléham_, Aug 18 2006
%e A091866 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].
%e A091866 Triangle begins:
%e A091866   1;
%e A091866   0,   1;
%e A091866   0,   0,   2;
%e A091866   0,   0,   1,   4;
%e A091866   0,   0,   1,   5,   8;
%e A091866   0,   0,   1,   7,  18,  16;
%e A091866   0,   0,   1,   9,  34,  56,  32;
%e A091866   0,   0,   1,  11,  55, 138, 160,  64;
%e A091866   0,   0,   1,  13,  81, 275, 500, 432, 128;
%e A091866   ...
%t A091866 nmax=11;
%t A091866 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}]];
%t A091866 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 *)
%K A091866 nonn,tabl
%O A091866 0,6
%A A091866 _Emeric Deutsch_, Mar 10 2004