A175962 Number of lattice paths from (0,0) to (n,n) using steps S={(k,0),(0,k),(r,r)|k>0,r>0} which never go above the line y=x.
1, 2, 10, 63, 454, 3539, 29008, 246255, 2145722, 19078536, 172402396, 1578687082, 14616730080, 136606848093, 1287022395324, 12210382758519, 116553763025178, 1118580919711060, 10786838228669692, 104469304517331666, 1015700422725526916
Offset: 0
Keywords
Links
- Vincenzo Librandi, Table of n, a(n) for n = 0..200
- Joseph P. S. Kung and Anna de Mier, Rook and queen paths with boundaries, arXiv:1109.1806 [math.CO], 2011.
- 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
Programs
-
Mathematica
Table[SeriesCoefficient[((1-t)*(1+t-4t^2)-(1-t)^2*Sqrt[1-12t+16t^2])/(2t*(2-3t)^2), {t,0,n}], {n,0,20}] (* Vaclav Kotesovec, Sep 07 2012 *) -
PARI
x='x+O('x^50); Vec(((1-t)*(1+t-4*t^2)-(1-t)^2*sqrt(1-12*t+16*t^2))/(2*t*(2 - 3*t)^2)) \\ G. C. Greubel, Mar 22 2017
Formula
G.f.: ((1-t)*(1+t-4*t^2)-(1-t)^2*sqrt(1-12*t+16*t^2))/(2*t*(2 - 3*t)^2). [Kung-de Mier]. - corrected by Vaclav Kotesovec, Sep 07 2012
Apparently 2*n*(n+1)*a(n) -n*(29*n-10)*a(n-1) +19*n*(5*n-7)*a(n-2) -2*n*(58*n-149)*a(n-3) +48*n*(n-4)*a(n-4)=0. - R. J. Mathar, Jul 24 2012
a(n) ~ 5/2*sqrt(246*sqrt(5)-550)/sqrt(Pi) * (6+2*sqrt(5))^n/n^(3/2). - Vaclav Kotesovec, Nov 01 2012
Equivalently, a(n) ~ 5^(5/4) * 2^(2*n) * phi^(2*n - 5) / (sqrt(Pi) * n^(3/2)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 08 2021
Extensions
Edited by N. J. A. Sloane, Sep 24 2011
Minor edits by Vaclav Kotesovec, Mar 31 2014