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

Author

Emeric Deutsch, May 08 2006

Keywords

• nonn

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

Examples

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

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.
• Emeric Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.

Crossrefs

Cf. A000108, A000957, A118972, A001558.

Programs

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 *)

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

my(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

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