A128748 Number of peaks at height >1 in all skew Dyck paths of semilength n.

0, 2, 11, 54, 260, 1247, 5982, 28741, 138364, 667488, 3226503, 15625476, 75802578, 368316888, 1792203759, 8732274312, 42598366616, 208036945958, 1017023261529, 4976560342522, 24372741339016, 119461561111023, 585970198529224

Offset

1,2

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.

Links

G. C. Greubel, Table of n, a(n) for n = 1..1000

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

Formula

a(n) = Sum_{k=0..n-1} A128747(n,k).

G.f.: (1-4*z+2*z^2+z^3-(1-z+z^2)*sqrt(1-6*z+5*z^2))/(2*z*(2-z)*sqrt(1-6*z+5*z^2)).

a(n) ~ 5^(n-1/2)/sqrt(Pi*n). - Vaclav Kotesovec, Mar 20 2014

D-finite with recurrence 2*(n+2)*a(n) +(-19*n-18)*a(n-1) +(53*n-12)*a(n-2) +2*(-20*n+19)*a(n-3) +(-n+26)*a(n-4) +5*(n-4)*a(n-5)=0. - R. J. Mathar, Jun 17 2016

Example

a(2)=2 because in the paths UDUD, U(UD)D and U(UD)L we have altogether 2 peaks at height >1 (shown between parentheses).

Maple

G:=(1-4*z+2*z^2+z^3-(1-z+z^2)*sqrt(1-6*z+5*z^2))/2/z/(2-z)/sqrt(1-6*z+5*z^2): Gser:=series(G, z=0, 30): seq(coeff(Gser, z, n), n=1..27);

Mathematica

Rest[CoefficientList[Series[(1-4*x+2*x^2+x^3-(1-x+x^2)*Sqrt[1-6*x+5*x^2]) /2/x/(2-x)/Sqrt[1-6*x+5*x^2], {x, 0, 20}], x]] (* Vaclav Kotesovec, Mar 20 2014 *)

Prog

(PARI) z='z+O('z^50); concat([0], Vec((1-4*z+2*z^2+z^3-(1-z+z^2)*sqrt(1-6*z+5*z^2))/(2*z*(2-z)*sqrt(1-6*z+5*z^2)))) \\ G. C. Greubel, Mar 20 2017

Crossrefs

Cf. A128747.

Sequence in context: A307568 A161559 A291386 * A251662 A327215 A307444

Adjacent sequences: A128745 A128746 A128747 * A128749 A128750 A128751

Keyword

nonn

Author

Emeric Deutsch, Mar 31 2007

Status

approved