A108447 - OEIS

%I #36 Jan 20 2025 02:34:53

%S 1,1,4,20,113,688,4404,29219,199140,1385904,9807820,70364704,

%T 510609620,3741212535,27639233548,205660399220,1539916433473,

%U 11594310041792,87725707127600,666681174728724,5086601816592432,38948589882247968

%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 have no peaks of the form ud.

%C Column 0 of A108446.

%H Seiichi Manyama, <a href="/A108447/b108447.txt">Table of n, a(n) for n = 0..1000</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 a(n) = (1/n) * Sum_{j=0..n} binomial(n, j)*binomial(n+2j, j-1) (n>=1); a(0)=1.

%F G.f.: G satisfies G = 1 + z*G*(G^2+G-1).

%F a(n) = hypergeom([1-n,(n+3)/2,(n+4)/2],[2,n+3],-4) for n>=1. - _Peter Luschny_, Oct 30 2015

%F a(n) ~ sqrt((s-1) / (Pi*(1 + 3*s))) / (2*n^(3/2) * r^(n + 1/2)), where r = 0.1215851068721183026145063923222031450327682505108... and s = 1.451605962955776643742608112028547116887657025022... are real roots of the system of equations 1 + r*s*(-1 + s + s^2) = s, r*(-1 + 2*s + 3*s^2) = 1. - _Vaclav Kotesovec_, Nov 27 2017

%F O.g.f.: A(x) = (1/x) * Revert( x/c(x/(1 - x)) ), where c(x) = (1 - sqrt(1 - 4*x))/(2*x) is the o.g.f. of the Catalan numbers A000108. - _Peter Bala_, Mar 08 2020

%F D-finite with recurrence 8*n*(2*n+1)*a(n) -6*(2*n-1)*(13*n-10)*a(n-1) +24*(4*n-7)*(2*n-5)*a(n-2) +4*(19*n-40)*(n-3)*a(n-3) -35*(n-3)*(n-4)*a(n-4)=0. - _R. J. Mathar_, Jul 26 2022

%e a(2)=4 because we have uUddd, UddUdd, UdUddd and UUdddd.

%p a:=n->(1/n)*sum(binomial(n,j)*binomial(n+2*j,j-1),j=0..n): 1, seq(a(n),n=1..25);

%p a := n -> `if`(n=0,1,simplify(hypergeom([1-n,(n+3)/2,(n+4)/2],[2, n+3],-4))): seq(a(n), n=0..21); # _Peter Luschny_, Oct 30 2015

%t Flatten[{1, Table[Sum[Binomial[n, j]*Binomial[n + 2*j, j-1], {j, 0, n}]/n, {n, 1, 20}]}] (* _Vaclav Kotesovec_, Nov 27 2017 *)

%t terms = 22; g[_] = 1; Do[g[x_] = 1+x*g[x]*(g[x]^2+g[x]-1) + O[x]^terms // Normal, {terms}]; CoefficientList[g[x], x] (* _Jean-François Alcover_, Jul 19 2018 *)

%Y Cf. A000108, A027307, A108446, A108425, A108426.

%K nonn

%O 0,3

%A _Emeric Deutsch_, Jun 10 2005