cp's OEIS Frontend

A118964 Triangle read by rows: T(n,k) is the number of Grand Dyck paths of semilength n that have k double rises above the x-axis (n >= 1, k >= 0).

%I A118964 #23 Jan 24 2025 08:49:37
%S A118964 2,5,1,14,5,1,42,19,8,1,132,67,40,12,1,429,232,166,79,17,1,1430,804,
%T A118964 634,395,145,23,1,4862,2806,2335,1708,879,249,30,1,16796,9878,8480,
%U A118964 6824,4376,1823,404,38,1,58786,35072,30691,26137,19334,10521,3542,625,47,1
%N A118964 Triangle read by rows: T(n,k) is the number of Grand Dyck paths of semilength n that have k double rises above the x-axis (n >= 1, k >= 0).
%C A118964 A Grand Dyck path of semilength n is a path in the half-plane x >= 0, starting at (0,0), ending at (2n,0) and consisting of steps u = (1,1) and d = (1,-1); a double rise in a Grand Dyck path is an occurrence of uu in the path.
%C A118964 For all double rises (above, below and on the x-axis), see A118963.
%H A118964 Alois P. Heinz, <a href="/A118964/b118964.txt">Rows n = 1..141, flattened</a>
%F A118964 Sum_{k>=0} k*T(n,k) = A000531(n-1).
%F A118964 G.f.: G(t,z) = (1+r)/[1-z(1+r)C]-1, where r = r(t,z) is the Narayana function, defined by (1+r)(1+tr)z = r, r(t,0) = 0 and C = C(z) = [1-sqrt(1-4z)]/(2z) is the Catalan function. More generally, the g.f. H = H(t,s,u,z), where t,s and u mark double rises above, below and on the x-axis, respectively, is H = [1 + r(s,z)]/[1 - z(1 + tr(t,z))(1 + ur(s,z))].
%e A118964 T(3,1) = 5 because we have u/ududd,u/uddud,udu/udd,duu/udd and u/udddu (the double rises above the x-axis are indicated by /).
%e A118964 Triangle starts:
%e A118964   2;
%e A118964   5,   1;
%e A118964   14,  5,  1;
%e A118964   42,  19, 8,  1;
%e A118964   132, 67, 40, 12, 1;
%p A118964 C:=(1-sqrt(1-4*z))/2/z: r:=(1-z-t*z-sqrt(z^2*t^2-2*z^2*t-2*z*t+z^2-2*z+1))/2/t/z: G:=(1+r)/(1-z*C*(1+r))-1: Gser:=simplify(series(G,z=0,15)): for n from 1 to 11 do P[n]:=coeff(Gser,z,n) od: for n from 1 to 11 do seq(coeff(P[n],t,j),j=0..n-1) od; # yields sequence in triangular form
%p A118964 # second Maple program:
%p A118964 b:= proc(x, y, t) option remember; `if`(abs(y)>x, 0,
%p A118964       `if`(x=0, 1, expand(`if`(t=2, z, 1)*b(x-1, y+1,
%p A118964       `if`(y>=0, min(t+1, 2), 1)) +b(x-1, y-1, 1))))
%p A118964     end:
%p A118964 T:= n-> (p-> seq(coeff(p,z,i), i=0..n-1))(b(2*n, 0, 1)):
%p A118964 seq(T(n), n=1..12);  # _Alois P. Heinz_, Jun 16 2014
%t A118964 b[x_, y_, t_] := b[x, y, t] = If[Abs[y] > x, 0, If[x == 0, 1, Expand[If[t == 2, z, 1]*b[x-1, y+1, If[y >= 0, Min[t+1, 2], 1]] + b[x-1, y-1, 1]]]]; T[n_] := Function[ {p}, Table[Coefficient[p, z, i], {i, 0, n-1}]][b[2*n, 0, 1]]; Table[T[n], {n, 1, 12}] // Flatten (* _Jean-François Alcover_, Feb 19 2015, after _Alois P. Heinz_ *)
%Y A118964 T(n,0) = A000108(n+1) (Catalan numbers), T(n,1) = A114277(n-2).
%Y A118964 Cf. A000984 (row sums), A000108, A000531, A118963.
%K A118964 nonn,tabl
%O A118964 1,1
%A A118964 _Emeric Deutsch_, May 07 2006
%E A118964 Keyword tabf changed to tabl by _Michel Marcus_, Apr 07 2013