A118973 Number of hill-free Dyck paths of semilength n+2 and having length of first descent equal to 2 (a hill in a Dyck path is a peak at level 1).

1, 0, 2, 5, 16, 51, 168, 565, 1934, 6716, 23604, 83806, 300154, 1083137, 3934404, 14374413, 52787766, 194746632, 721435884, 2682522918, 10008240456, 37455101382, 140569122624, 528926230530, 1994980278636, 7541234323096

Offset

0,3

Comments

Also, for a given j>=2, number of hill-free Dyck paths of semilength n+j and having length of first descent equal to j. a(n)=A000108(n+1)-A000108(n)-[A000957(n+2)-A000957(n+1)]. Columns 2,3,4,... of A118972 (without the initial 0's).

Links

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

Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.

E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

Formula

G.f.: (1-x)*C*F, where F = (1-sqrt(1-4*x))/(x*(3-sqrt(1-4*x)) and C = (1-sqrt(1-4*x))/(2*x) is the Catalan function.

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

a(n) = (Sum_{k=0..n-1}((k+2)*(-1)^k*(binomial(2*n-k+1,n-k)/(n+2)-binomial(2*n-k-1,n-k-1)/(n+1))))+(-1)^(n). - Vladimir Kruchinin. Mar 06 2016

D-finite with recurrence +2*(n+2)*a(n) +(-7*n-2)*a(n-1) +2*(-3*n+1)*a(n-2) +(7*n-26)*a(n-3) +2*(2*n-7)*a(n-4)=0. - R. J. Mathar, Jul 26 2022

Example

a(2)=2 because we have uu(dd)uudd and uuu(dd)udd, where u=(1,1),d=(1,-1) (the first descents are shown between parentheses).

Maple

F:=(1-sqrt(1-4*z))/z/(3-sqrt(1-4*z)): C:=(1-sqrt(1-4*z))/2/z: g:=(1-z)*C*F: gser:=series(g, z=0, 33): seq(coeff(gser, z, n), n=0..28);
A118973List := proc(m) local A, P, n; A := [1, 0]; P := [1, 0];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-2]]);
A := [op(A), P[-1]] od; A end: A118973List(26); # Peter Luschny, Mar 26 2022

Mathematica

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

Prog

(Maxima)
a(n):=(sum((k+2)*(-1)^k*(binomial(2*n-k+1, n-k)/(n+2)-binomial(2*n-k-1, n-k-1)/(n+1)), k, 0, n-1))+(-1)^(n); /*  Vladimir Kruchinin. Mar 06 2016 */
(PARI) x='x+O('x^25); Vec((1-x)*(1-sqrt(1-4*x))/x/(3-sqrt(1-4*x))*(1-sqrt(1-4*x))/2/x) \\ G. C. Greubel, Feb 08 2017

Crossrefs

Cf. A000108, A000957, A118972, A001558.

Sequence in context: A148384 A148385 A205501 * A148386 A148387 A121651

Adjacent sequences: A118970 A118971 A118972 * A118974 A118975 A118976

Keyword

nonn

Author

Emeric Deutsch, May 08 2006

Status

approved