A107708 Number of paths from (0,0) to (3n,0) that stay in the first quadrant (x,y >= 0) and where each step is (3,0), (2,1), (1,2), or (1,-1).
1, 3, 18, 144, 1323, 13176, 138348, 1507977, 16900650, 193536864, 2254630788, 26635735440, 318350663748, 3842488208997, 46770206742342, 573435609537600, 7075551692662875, 87794803094586336, 1094807464312435344
Offset: 0
Keywords
Examples
a(1)=3 because we have H, uD and Udd, where H=(3,0), u=(2,1), U=(1,2) and D=(1,-1).
Links
- G. C. Greubel, Table of n, a(n) for n = 0..880
- Emeric Deutsch, Problem 10658, American Math. Monthly, 107, 2000, 368-370.
- M. Dziemianczuk, Counting Lattice Paths With Four Types of Steps, Graphs and Combinatorics, September 2013, DOI 10.1007/s00373-013-1357-1.
Programs
-
Maple
a:=n->(1/n)*sum(3^j*binomial(n,j)*binomial(n+j,2*n+1-j),j=ceil((n+1)/2)..n): 1,seq(a(n),n=1..22);
-
Mathematica
Flatten[{1,Table[1/n*Sum[3^j*Binomial[n, j]*Binomial[n+j, 2n+1-j], {j,Floor[(n+1)/2],n}],{n,1,20}]}] (* Vaclav Kotesovec, Mar 17 2014 *) -
PARI
concat([1], for(n=1,50, print1((1/n)*sum(j=floor((n+1)/2),n, 3^j*binomial(n,j)*binomial(n+j,2*n+1-j)), ", "))) \\ G. C. Greubel, Mar 16 2017
Formula
a(n) = (1/n)*Sum(3^j*binomial(n, j)*binomial(n+j, 2n+1-j), j=ceiling((n+1)/2)..n) for n >= 1; a(0)=1.
G.f. = (2/3)w*sin((1/3)*arcsin((36-7z)/2/(3-2z)/w))-1/3, where w=sqrt((3-2z)/z).
Recurrence: 2*n*(2*n+1)*(17*n-25)*a(n) = 4*(238*n^3 - 588*n^2 + 395*n - 72)*a(n-1) - 12*(n-2)*(34*n^2 - 67*n + 21)*a(n-2) + 3*(n-3)*(n-2)*(17*n - 8)*a(n-3). - Vaclav Kotesovec, Mar 17 2014
a(n) ~ (1/204)*sqrt(102)*sqrt((134963 + 21573*sqrt(17))^(1/3) * ((134963 + 21573*sqrt(17))^(2/3) + 2176 + 68*(134963 + 21573*sqrt(17))^(1/3))) / ((134963 + 21573*sqrt(17))^(1/3)*sqrt(Pi)) * 6^(-n) * ((19009 + 153*sqrt(17))^(2/3) + 712 + 28*(19009 + 153*sqrt(17))^(1/3))^n * (19009 + 153*sqrt(17))^(-n/3)*(1/n)^(3/2). - Vaclav Kotesovec, Mar 17 2014
D-finite with recurrence 8*n*(2*n+1)*a(n) +2*(-106*n^2+97*n-18)*a(n-1) +36*(-2*n^2+12*n-15)*a(n-2) +12*(5*n-14)*(n-3)*a(n-3) -9*(n-3)*(n-4)*a(n-4)=0. - R. J. Mathar, Jul 26 2022
G.f. satisfies A(x) = 1 + x * A(x) * (1 + A(x) + A(x)^2). - Seiichi Manyama, Apr 01 2024