A128718 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k UU's (doublerises) (n >= 1; 0 <= k <= n-1).

1, 1, 2, 1, 5, 4, 1, 9, 18, 8, 1, 14, 50, 56, 16, 1, 20, 110, 220, 160, 32, 1, 27, 210, 645, 840, 432, 64, 1, 35, 364, 1575, 3150, 2912, 1120, 128, 1, 44, 588, 3388, 9534, 13552, 9408, 2816, 256, 1, 54, 900, 6636, 24822, 49644, 53088, 28800, 6912, 512, 1, 65, 1320, 12090, 57750, 153426, 231000, 193440, 84480, 16640, 1024

Offset

1,3

Comments

A skew Dyck path is a path in the first quadrant which begins at the origin, ends on the x-axis, consists of steps U=(1,1)(up), D=(1,-1)(down) and L=(-1,-1)(left) so that up and left steps do not overlap. The length of a path is defined to be the number of its steps.

Row sums yield A002212.

Links

Table of n, a(n) for n=1..66.

E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203.

Formula

T(n,0) = 1;

T(n,1) = (n-1)(n+2)/2 = A000096(n-1);

T(n,k) = A126182(n,n-k), i.e., triangle is mirror image of A126182.

Sum_{k=0..n-1} k*T(n,k) = A128743(n).

T(n,k) = (binomial(n,k)/n)*Sum_{j=0..k} binomial(k,j)*binomial(n-k+j, j+1) (1 <= k <= n).

G.f.: G - 1, where G = G(t,z) satisfies G = 1 + tzG^2 + zG - tz.

Example

T(3,2)=4 because we have UUUDDD, UUUDLD, UUUDDL and UUUDLL.
Triangle starts:
  1;
  1,  2;
  1,  5,  4;
  1,  9, 18,  8;
  1, 14, 50, 56, 16;

Maple

T:=proc(n, k) if k=0 then 1 else binomial(n, k)*sum(binomial(k, j)*binomial(n-k+j, j+1), j=0..k)/n fi end: for n from 1 to 11 do seq(T(n, k), k=0..n-1) od; # yields sequence in triangular form

Mathematica

m = 12; G[_] = 0;
Do[G[z_] = 1 + t z G[z]^2 + z G[z] - t z + O[z]^m, {m}];
CoefficientList[#, t]& /@ CoefficientList[G[z], z] // Rest // Flatten (* Jean-François Alcover, Nov 15 2019 *)

Crossrefs

Cf. A000096, A002212, A126182, A128743.

Sequence in context: A366156 A056242 A343960 * A112358 A126351 A157011

Adjacent sequences: A128715 A128716 A128717 * A128719 A128720 A128721

Keyword

nonn,tabl

Author

Emeric Deutsch, Mar 30 2007

Status

approved