login
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).
2
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
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
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Mar 30 2007
STATUS
approved