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
Keywords
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.
Programs
-
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 *)
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
Extensions
Minor edits Vaclav Kotesovec, Mar 31 2014