login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A128722
Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k hills (i.e., peaks at level 1) (0 <= k <= n).
1
1, 0, 1, 2, 0, 1, 6, 3, 0, 1, 22, 9, 4, 0, 1, 84, 35, 12, 5, 0, 1, 334, 138, 49, 15, 6, 0, 1, 1368, 563, 198, 64, 18, 7, 0, 1, 5734, 2352, 825, 264, 80, 21, 8, 0, 1, 24480, 10015, 3504, 1121, 336, 97, 24, 9, 0, 1, 106086, 43308, 15123, 4833, 1452, 414, 115, 27, 10, 0, 1
OFFSET
0,4
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.
T(n,0) = A128723(n).
Row sums yield A002212.
Sum_{k=0..n} k*T(n,k) = A033321(n).
LINKS
E. Deutsch, E. Munarini, S. Rinaldi, Skew Dyck paths, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203
FORMULA
G.f.: (1-z+zg)/(1+z-zg-tz), where g = 1+zg^2+z(g-1) = (1-z-sqrt(1-6z+5z^2))/(2z).
EXAMPLE
T(3,1)=3 because we have (UD)UUDD, (UD)UUDL and UUDD(UD) (the hills are shown between parentheses).
Triangle starts:
1;
0, 1;
2, 0, 1;
6, 3, 0, 1;
22, 9, 4, 0, 1;
84, 35, 12, 5, 0, 1;
MAPLE
g:=(1-z-sqrt(1-6*z+5*z^2))/2/z: G:=(1-z+z*g)/(1+z-z*g-t*z): Gser:=simplify(series(G, z=0, 14)): for n from 0 to 12 do P[n]:=sort(coeff(Gser, z, n)) od: for n from 0 to 11 do seq(coeff(P[n], t, j), j=0..n) od; # yields sequence in triangular form
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Mar 30 2007
STATUS
approved