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

1, 3, 10, 33, 111, 379, 1312, 4596, 16266, 58082, 209010, 757259, 2760123, 10114131, 37239072, 137698584, 511140558, 1904038986, 7115422212, 26668376994, 100221202998, 377570383518, 1425706128480, 5394898197448, 20454676622476

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy

Comments

a(n) is also the number of even-length descents to ground level in all Dyck paths of semilength n+2. Example: a(1)=3 because in UDUDUD, UDUU(DD), UU(DD)UD, UUDU(DD) and UUUDDD we have 3 even-length descents to ground level (shown between parentheses). - Emeric Deutsch, Oct 05 2008

Convolution of A000108 with A104629. - Philippe Deléham, Nov 11 2009

The Kn12 triangle sums of A039599 are given by the terms of this sequence. For the definition of this and other triangle sums see A180662. - Johannes W. Meijer, Apr 20 2011

Examples

			a(1)=3 because we have uu(d)ududd, uuu(d)uddd and uu(d)uuddd, where u=(1,1), d=(1,-1) (the first descents are shown between parentheses).
G.f. = 1 + 3*x + 10*x^2 + 33*x^3 + 111*x^4 + 379*x^5 + 1312*x^6 + ...
		

References

• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• E. Deutsch and L. Shapiro, A survey of the Fine numbers, Discrete Math., 241 (2001), 241-265.
• T. Fine, Extrapolation when very little is known about the source, Information and Control 16 (1970), 331-359.
• Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
• Simon Plouffe, Une méthode pour obtenir la fonction génératrice d'une série. FPSAC 1993, Florence. Formal Power Series and Algebraic Combinatorics.
• Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016. See Appendix B2.

Crossrefs

Cf. A000957, A118972, A118973.

Cf. A111301. - Emeric Deutsch, Oct 05 2008

Programs

Magma

m:=30; R:=PowerSeriesRing(Rationals(), m); Coefficients(R!( (1-Sqrt(1-4*x))/(x*(3-Sqrt(1-4*x)))*((1-Sqrt(1-4*x))/(2*x))^3 )); // G. C. Greubel, Feb 12 2019

Maple

F:=(1-sqrt(1-4*z))/z/(3-sqrt(1-4*z)): C:=(1-sqrt(1-4*z))/2/z: g:=F*C^3: gser:=series(g,z=0,32): seq(coeff(gser,z,n),n=0..27); # Emeric Deutsch, May 08 2006

Mathematica

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

PARI

my(x='x+O('x^30)); Vec((1-sqrt(1-4*x))/(x*(3-sqrt(1-4*x)))*((1-sqrt(1-4*x))/(2*x))^3) \\ G. C. Greubel, Feb 12 2019

Sage

((1-sqrt(1-4*x))/(x*(3-sqrt(1-4*x)))*((1-sqrt(1-4*x))/(2*x))^3).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Feb 12 2019

Formula

a(n) = A000957(n+4) - A000957(n+3) - A000957(n+2) (A000957 are the Fine numbers). - Emeric Deutsch, May 08 2006

a(n) = A118972(n+3,1). - Emeric Deutsch, May 08 2006

G.f.: F*C^3, where F = (1-sqrt(1-4z))/(z*(3-sqrt(1-4z))) and C = (1-sqrt(1-4z))/(2z) is the Catalan function. - Emeric Deutsch, May 08 2006

a(n) = Sum_{k>=0} k*A111301(n+2,k). - Emeric Deutsch, Oct 05 2008

(n+3)*a(n) = (-(11/2)*n + 21/2)*a(n-3) + ((9/2)*n + 11/2)*a(n-1) + (-(1/2)*n + 9/2)*a(n-2) + (-2n + 5)*a(n-4). - Simon Plouffe, Feb 09 2012

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

Extensions

Edited by Emeric Deutsch, May 08 2006