A129163 - OEIS

%I #9 Dec 02 2014 16:49:32

%S 1,1,2,2,4,4,4,11,13,8,8,29,46,38,16,16,74,150,167,104,32,32,184,461,

%T 652,554,272,64,64,448,1354,2344,2535,1724,688,128,128,1072,3836,7922,

%U 10462,9103,5112,1696,256,256,2528,10552,25506,40007,42547,30773,14592

%N Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and pyramid weight k.

%C 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.

%C 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).

%H A. Denise and R. Simion, <a href="http://dx.doi.org/10.1016/0012-365X(93)E0147-V">Two combinatorial statistics on Dyck paths</a>, Discrete Math., 137, 1995, 155-176.

%H E. Deutsch, E. Munarini, S. Rinaldi, <a href="http://dx.doi.org/10.1016/j.jspi.2010.01.015">Skew Dyck paths</a>, J. Stat. Plann. Infer. 140 (8) (2010) 2191-2203

%F 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.

%e 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).

%e Triangle starts:

%e 1;

%e 1,2;

%e 2,4,4;

%e 4,11,13,8;

%e 8,29,46,38,16;

%p 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

%Y Cf. A002212, A129164.

%K nonn,tabl

%O 1,3

%A _Emeric Deutsch_, Apr 03 2007