A108430 Number of d steps in all paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(2,1), U=(1,2), or d=(1,-1).
3, 31, 311, 3151, 32299, 334335, 3488239, 36627487, 386618387, 4098713631, 43611791783, 465496885231, 4981942135611, 53443871159551, 574500093677535, 6186886528903231, 66735614131858723, 720897596248427295
Offset: 1
Keywords
Examples
a(1) = 3 because in the paths ud, Udd we have 3 d steps altogether.
Links
- Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.
Programs
-
Maple
a:=n->(1/n)*sum(k*binomial(n,2*n-k)*binomial(n+k,n-1),k=n..2*n): seq(a(n),n=1..22);
Formula
a(n) = (1/n)*sum(k*binomial(n,2n-k)*binomial(n+k,n-1), k=n..2n).
Conjecture D-finite with recurrence n*(2*n+1)*(23982*n-28681)*a(n) +(-640736*n^3+1168048*n^2-901220*n+247035)*a(n-1) +(1196488*n^3-6448608*n^2+10992587*n-5911365)*a(n-2) +2*(2*n-5)*(28283*n-6993)*(n-3)*a(n-3)=0. - R. J. Mathar, Jul 24 2022