A107708 - OEIS

%I #25 Apr 02 2024 02:58:12

%S 1,3,18,144,1323,13176,138348,1507977,16900650,193536864,2254630788,

%T 26635735440,318350663748,3842488208997,46770206742342,

%U 573435609537600,7075551692662875,87794803094586336,1094807464312435344

%N 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).

%H G. C. Greubel, <a href="/A107708/b107708.txt">Table of n, a(n) for n = 0..880</a>

%H Emeric Deutsch, <a href="http://www.jstor.org/stable/2589192">Problem 10658</a>, American Math. Monthly, 107, 2000, 368-370.

%H M. Dziemianczuk, <a href="http://dx.doi.org/10.1007/s00373-013-1357-1">Counting Lattice Paths With Four Types of Steps</a>, Graphs and Combinatorics, September 2013, DOI 10.1007/s00373-013-1357-1.

%F 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.

%F G.f. = (2/3)w*sin((1/3)*arcsin((36-7z)/2/(3-2z)/w))-1/3, where w=sqrt((3-2z)/z).

%F 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

%F 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

%F 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

%F G.f. satisfies A(x) = 1 + x * A(x) * (1 + A(x) + A(x)^2). - _Seiichi Manyama_, Apr 01 2024

%e a(1)=3 because we have H, uD and Udd, where H=(3,0), u=(2,1), U=(1,2) and D=(1,-1).

%p 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);

%t 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 *)

%o (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

%Y Cf. A027307, A106228, A346626.

%K nonn

%O 0,2

%A _Emeric Deutsch_, Jun 10 2005