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.

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

Author

N. J. A. Sloane

Keywords

• nonn

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

Examples

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

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.

Programs

Magma

R:=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

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

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

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

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

Extensions

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