|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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.
|
|
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);
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
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|