login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A128741 Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k returns to the x-axis (1 <= k <= n). 0

%I

%S 1,2,1,6,3,1,20,11,4,1,72,42,17,5,1,274,166,72,24,6,1,1086,675,307,

%T 111,32,7,1,4438,2809,1322,506,160,41,8,1,18570,11913,5752,2296,775,

%U 220,51,9,1,79174,51319,25274,10418,3692,1127,292,62,10,1,342738,223977,112054

%N Triangle read by rows: T(n,k) is the number of skew Dyck paths of semilength n and having k returns to the x-axis (1 <= k <= n).

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

%C Row sums yield A002212.

%C T(n,1) = 2*A002212(n-1) for n >= 2 (obvious: the path of semilength n with exactly one return are of the form UPD and UPL, where P is a path of semilength n-1).

%C Sum_{k=1..n} k*T(n,k) = A128742(n).

%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.: (1 - tz + tzg)/(1 - tzg) - 1, where g = 1 + zg^2 + z(g-1) = (1 - z - sqrt(1 - 6z + 5z^2))/(2z).

%F Column k has g.f. z^k*g^(k-1)*(2g-1).

%e T(4,3)=4 because we have U(D)U(D)UUD(D), U(D)U(D)UUD(L), U(D)UUD(D)U(D) and UUD(D)U(D)U(D) (the return steps to the x-axis are shown between parentheses).

%e Triangle starts:

%e 1;

%e 2, 1;

%e 6, 3, 1;

%e 20, 11, 4, 1;

%e 72, 42, 17, 5, 1;

%p g:=(1-z-sqrt(1-6*z+5*z^2))/2/z: G:=(1-t*z+t*z*g)/(1-t*z*g)-1: Gser:=simplify(series(G,z=0,15)): for n from 1 to 13 do P[n]:=sort(coeff(Gser,z,n),n=1..11) od: for n from 1 to 11 do seq(coeff(P[n],t,j),j=1..n) od;

%Y Cf. A002212, A128742.

%K tabl,nonn

%O 1,2

%A _Emeric Deutsch_, Mar 31 2007

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 25 19:09 EST 2020. Contains 331249 sequences. (Running on oeis4.)