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

2, 3, 3, 4, 12, 4, 5, 30, 30, 5, 6, 60, 120, 60, 6, 7, 105, 350, 350, 105, 7, 8, 168, 840, 1400, 840, 168, 8, 9, 252, 1764, 4410, 4410, 1764, 252, 9, 10, 360, 3360, 11760, 17640, 11760, 3360, 360, 10, 11, 495, 5940, 27720, 58212, 58212, 27720, 5940, 495, 11, 12

Offset: 1

Author

Emeric Deutsch, May 07 2006

Keywords

• nonn
• tabl

Comments

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.

For double rises only above the x-axis see A118964.

This is the triangle of Narayana with row n multiplied by n + 1. - Peter Luschny, May 02 2022

Examples

			T(3,2)=4 because we have uuuddd, duuudd, dduuud and ddduuu.
Triangle begins:
  2;
  3,    3;
  4,   12,    4;
  5,   30,   30,    5;
  6,   60,  120,   60,    6;
  7,  105,  350,  350,  105,    7;
  8,  168,  840, 1400,  840,  168,    8;
  9,  252, 1764, 4410, 4410, 1764,  252,    9;
		

Crossrefs

Cf. A000917, A000984 (row sums), A027480, A027789, A118964, A001263.

Programs

Maple

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)^2/(1-t*r^2)-1: Gser:=simplify(series(G,z=0,15)): for n from 1 to 11 do P[n]:=sort(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
for n from 0 to 10 do seq(binomial(n,i)*binomial(n+2,n+1-i), i=0..n ); od; # Zerinvary Lajos, Nov 03 2006

Formula

T(n,1) = n(n^2 - 1)/2 (A027480).

T(n,2) = (n+1)n(n-1)^2*(n-2)/12 (A027789).

T(n,k) = ((n+1)/n)*binomial(n,k)*binomial(n,k+1).

Sum_{k>=0} k*T(n,k) = (2n-1)!/(n!(n-2)!) (A000917).

G.f.: G(t,z) = (1+r)^2/(1 - tr^2) - 1, where r = r(t,z) is the Narayana function, defined by (1+r)(1+tr)z = r, r(t,0) = 0. 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))).

Row n is given by seq(binomial(n, k)*binomial(n+2, n+1-k), k=0..n). - Zerinvary Lajos, Nov 03 2006

T(n,k)/(n+1) = A001263(n,k). - Peter Luschny, May 02 2022