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). (Formerly M2845 N1143)

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,2

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

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.

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

Example

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

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

Prog

(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
(Magma) m:=30; R<x>:=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
(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

Crossrefs

Cf. A000957, A118972, A118973.

Cf. A111301. - Emeric Deutsch, Oct 05 2008

Sequence in context: A257363 A071722 A058987 * A304824 A111639 A302076

Adjacent sequences: A001555 A001556 A001557 * A001559 A001560 A001561

Keyword

nonn,easy

Author

N. J. A. Sloane

Extensions

Edited by Emeric Deutsch, May 08 2006

Status

approved