A175912 Number of lattice paths from (0,0) to (n,n) using steps S={(k,0),(0,k),(1,1)|k>0} which never go above the line y=x.

1, 2, 9, 57, 411, 3181, 25803, 216486, 1863139, 16356925, 145914573, 1318844414, 12051758083, 111159508991, 1033505202643, 9675905948106, 91140492185703, 863107104436546, 8212873185281571, 78484928498979435, 752928813642151089

Offset

0,2

Links

Vincenzo Librandi, Table of n, a(n) for n = 0..200

J. P. S. Kung and A. de Mier, Catalan lattice paths with rook, bishop and spider steps, Journal of Combinatorial Theory, Series A 120 (2013) 379-389. - From N. J. A. Sloane, Dec 27 2012

Joseph P. S. Kung, Anna de Mier, Rook and queen paths with boundaries, arXiv:1109.1806.

Formula

Asymptotic: a(n) ~ b*c^n/n^(3/2), where c = 10.33185141266662366... is the root of the equation c^3-11*c^2+7*c-1=0 and b = sqrt(13*c-5-c^2)*(2*c^2+9*c-2)/(2*c^3*sqrt(Pi)) = 0.36996178... - Vaclav Kotesovec, Dec 25 2013

G.f. (from reference): (1+2*x-x^2 - sqrt((x-1)*(x^3-7*x^2+11*x-1)))/(2*x*(x-2)^2). - Vaclav Kotesovec, Dec 25 2013

Mathematica

Flatten[{1, RecurrenceTable[{(n+1)*a[n]-10*(n+2)*a[n+1]+(34*n+96)*a[n+2]-6*(8*n+29)*a[n+3]+5*(5*n+23)*a[n+4]-2*(n+6)*a[n+5]==0, a[1]==2, a[2]==9, a[3]==57, a[4]==411, a[5]==3181}, a, {n, 20}]}] (* Vaclav Kotesovec, Sep 07 2012 *)

Crossrefs

Cf. A006318, A175895, A175896, A175900.

Sequence in context: A223381 A175896 A175900 * A218824 A111545 A070075

Adjacent sequences: A175909 A175910 A175911 * A175913 A175914 A175915

Keyword

nonn

Author

Eric Werley, Dec 05 2010

Extensions

Minor edits Vaclav Kotesovec, Mar 31 2014

Status

approved