A108442 - OEIS

%I #23 Jul 26 2022 14:19:17

%S 1,1,3,15,97,721,5827,49759,441729,4035937,37702723,358474735,

%T 3457592161,33748593841,332730216579,3308635650495,33145196426753,

%U 334193815799233,3388807714823043,34537227997917391,353578650475659617,3634495706671023505,37496621681376849219,388135791657414454815

%N Number of 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) and having only u steps among the steps leading to the first d step.

%H G. C. Greubel, <a href="/A108442/b108442.txt">Table of n, a(n) for n = 0..955</a>

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

%F G.f.: 1/(1-z*A), where A = 1 + z*A^2 + z*A^3 = (2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3 (the g.f. of A027307).

%F a(n) = Sum_{k=1..n} (k*(Sum_{i=0..n-k} binomial(2*n-k, i)*binomial(3*n-2*k-i-1, 2*n-k-1))/(2*n-k)), n > 0, a(0)=1. - _Vladimir Kruchinin_, Oct 23 2011

%F G.f. y(x) satisfies: (3+x)*y*(1-y) + (1+x^2)*y^3 = 1. - _Vaclav Kotesovec_, Mar 17 2014

%F a(n) ~ (11+5*sqrt(5))^n / (5^(5/4) * sqrt(Pi) * n^(3/2) * 2^(n+1)). - _Vaclav Kotesovec_, Mar 17 2014

%F D-finite with recurrence (2*n-1)*(n-1)*a(n) +6*(n^2-10*n+13)*a(n-1) +(-310*n^2+1869*n-2759)*a(n-2) +48*(-n+3)*a(n-3) +(-310*n^2+1851*n-2705)*a(n-4) +6*(-n^2+2*n+11)*a(n-5) +(n-5)*(2*n-11)*a(n-6)=0. - _R. J. Mathar_, Jul 26 2022

%e a(2)=3 because we have udud, udUdd and uudd.

%p A:=(2/3)*sqrt((z+3)/z)*sin((1/3)*arcsin(sqrt(z)*(z+18)/(z+3)^(3/2)))-1/3: gser:=series(1/(1-z*A),z=0,30): 1,seq(coeff(gser,z^n),n=1..25);

%t Flatten[{1,Table[Sum[k*Sum[Binomial[2*n-k, i]*Binomial[3*n-2*k-i-1, 2*n-k-1], {i, 0, n-k}]/(2*n-k), {k, 1, n}],{n,1,20}]}] (* _Vaclav Kotesovec_, Mar 17 2014, after _Vladimir Kruchinin_ *)

%o (Maxima)

%o a(n):=if n=0 then 1 else sum((k*sum(binomial(2*n-k,i)*binomial(3*n-2*k-i-1,2*n-k-1),i,0,n-k))/(2*n-k),k,1,n); /* _Vladimir Kruchinin_, Oct 23 2011 */

%Y Column 0 of A108441.

%Y Cf. A027307, A108441.

%K nonn

%O 0,3

%A _Emeric Deutsch_, Jun 08 2005