A001559 a(0) = 1, a(1) = 4; thereafter a(n)*(2n + 10) - a(n-1)*(11n + 35) + a(n-2)*(8n + 2) + a(n-3)*(15n + 7) + a(n-4)*(4n - 2) = 0. (Formerly M3497 N1418)

1, 4, 15, 54, 193, 690, 2476, 8928, 32358, 117866, 431381, 1585842, 5853849, 21690378, 80650536, 300845232, 1125555054, 4222603968, 15881652606, 59873283372, 226214536506, 856431978324, 3248562071800, 12344168149224, 46984664348488, 179114048943078

Offset

0,2

Comments

Apparently, the number of hill-free Dyck (n+4)-paths with at least two returns. E.g., the a(1)=4 hill-free 5-paths are UUUDDDUUDD, UUDUDDUUDD, UUDDUUUDDD and UUDDUUDUDD with 2 returns each. - David Scambler, Aug 26 2012

References

Terrence Fine, Extrapolation when very little is known about the source. Information and Control 16 (1970), 331-359.

Ki Hang Kim, Douglas G. Rogers, and Fred W. Roush, Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577-594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013) - From N. J. A. Sloane, Jun 05 2012

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

T. D. Noe, Table of n, a(n) for n = 0..200

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; arXiv:0912.0072 [math.NT], 2009.

D. G. Rogers, Similarity relations on finite ordered sets, J. Combin. Theory, Series A, Vol. 23, No. 1 (1977), pp. 88-98. Erratum, loc. cit., Vol. 25 (1978), pp. 95-96.

Formula

0 = -a(n) * n * (2*n + 10) * (7*n + 13) + a(n-1) * (49*n^3 + 252*n^2 + 419*n + 240) + a(n-2) * (2*n + 2) * (2*n + 3) * (7*n + 20). - Michael Somos, Jul 14 2009

G.f.: 2 / (1 - 4*x + x^2 + 2*x^3 + (1 - 2*x - x^2) * sqrt(1 - 4*x )). - Michael Somos, Jul 14 2009

(n+4)*a(n) = (-(15/2)*n + 4)*a(n-3) + ((11/2)*n + 12)*a(n-1)

+ (-4*n + 3)*a(n-2) + (-2*n + 3)*a(n-4). - Simon Plouffe, Feb 09 2012

a(n) ~ 7*2^(2*n+6)/(9*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Aug 13 2013

0 = a(n) * (-112336*a(n+1) - 30270*a(n+2) - 88504*a(n+3) - 845858*a(n+4) + 217516*a(n+5)) + a(n+1) * (-14042*a(n+1) + 440283*a(n+2) - 328994*a(n+3) - 731173*a(n+4) + 230486*a(n+5)) + a(n+2) * (38900*a(n+2) - 812130*a(n+3) + 1877788*a(n+4) - 386672*a(n+5)) + a(n+3) * (-535412*a(n+3) - 86596*a(n+4) + 44840*a(n+5)) if n > -3. - Michael Somos, Apr 03 2014

Example

G.f. = 1 + 4*x + 15*x^2 + 54*x^3 + 193*x^4 + 690*x^5 + 2476*x^6 + 8928*x^7 + ...

Mathematica

nn = 20; a[-2] = 0; a[-1] = 0; a[0] = 1; a[1] = 4; Do[a[n] = (a[n - 1]*(11*n + 35) - a[n - 2]*(8*n + 2) - a[n - 3]*(15*n + 7) - a[n - 4]*(4*n - 2))/(2*n + 10), {n, 2, nn}]; Table[a[n], {n, 0, nn}] (* T. D. Noe, May 09 2012 *)
CoefficientList[Series[2/(1-4*x+x^2+2*x^3 +(1-2*x-x^2)*Sqrt[1-4*x]), {x, 0, 30}], x] (* G. C. Greubel, Apr 28 2019 *)

Prog

(PARI) {a(n) = if( n<0, 0, polcoeff( 2 / (1 - 4*x + x^2 + 2*x^3 + (1 - 2*x - x^2) * sqrt(1 - 4*x + x*O(x^n))), n))}; /* Michael Somos, Jul 14 2009 */
(Magma) R<x>:=PowerSeriesRing(Rationals(), 30); Coefficients(R!( 2/(1-4*x +x^2+2*x^3 +(1-2*x-x^2)*Sqrt(1-4*x)) )); // G. C. Greubel, Apr 28 2019
(Sage) (2/(1-4*x+x^2+2*x^3 +(1-2*x-x^2)*sqrt(1-4*x))).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Apr 28 2019

Crossrefs

Sequence in context: A006234 A094821 A071723 * A002311 A102349 A219603

Adjacent sequences: A001556 A001557 A001558 * A001560 A001561 A001562

Keyword

nonn

Author

N. J. A. Sloane

Extensions

Better definition and more terms from Michael Somos, Jul 14 2009

Status

approved