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”).

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

%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