login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A129163 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and pyramid weight k. 1
1, 1, 2, 2, 4, 4, 4, 11, 13, 8, 8, 29, 46, 38, 16, 16, 74, 150, 167, 104, 32, 32, 184, 461, 652, 554, 272, 64, 64, 448, 1354, 2344, 2535, 1724, 688, 128, 128, 1072, 3836, 7922, 10462, 9103, 5112, 1696, 256, 256, 2528, 10552, 25506, 40007, 42547, 30773, 14592 (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 the path is defined to be the number of its steps. A pyramid in a skew Dyck word (path) is a factor of the form U^h D^h, h being the height of the pyramid. A pyramid in a skew Dyck word w is maximal if, as a factor in w, it is not immediately preceded by a U and immediately followed by a D. The pyramid weight of a skew Dyck path (word) is the sum of the heights of its maximal pyramids.

Row sums yield A002212. T(n,1)=2^(n-2) (n>=2). T(n,n)=2^(n-1). Sum(k*T(n,k),k=1..n)=A129164(n). Pyramid weight in Dyck paths is considered in the Denise and Simion reference (see also A091866).

LINKS

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

A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176.

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

FORMULA

G.f.=G-1, where G=G(t,z) is given by z(1-tz)G^2-(1-2tz+tz^2)G+(1-z)(1-tz)=0.

EXAMPLE

T(3,2)=4 because we have (UD)U(UD)L, U(UD)(UD)D, U(UD)(UD)L and U(UUDD)L (the maximal pyramids are shown between parentheses).

Triangle starts:

1;

1,2;

2,4,4;

4,11,13,8;

8,29,46,38,16;

MAPLE

eq:=z*(1-t*z)*G^2-(1-2*t*z+t*z^2)*G+(1-z)*(1-t*z)=0: G:=RootOf(eq, G): Gser:=simplify(series(G-1, z=0, 15)): for n from 1 to 11 do P[n]:=sort(expand(coeff(Gser, z, n))) od: for n from 1 to 11 do seq(coeff(P[n], t, j), j=1..n) od; # yields sequence in triangular form

CROSSREFS

Cf. A002212, A129164.

Sequence in context: A220461 A220287 A320195 * A083549 A083548 A082849

Adjacent sequences:  A129160 A129161 A129162 * A129164 A129165 A129166

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Apr 03 2007

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 20 10:18 EST 2022. Contains 350471 sequences. (Running on oeis4.)