login
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 no pyramids of the first kind (a pyramid of the first kind is a sequence u^pd^p for some positive integer p, starting at the x-axis).
2

%I #13 Jul 26 2022 12:27:05

%S 1,1,6,44,344,2856,24816,223016,2056256,19344472,184956240,1792088296,

%T 17558218048,173659691928,1731556718224,17387182158184,

%U 175670235597120,1784561125349464,18216639085961552,186762117058304104

%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 no pyramids of the first kind (a pyramid of the first kind is a sequence u^pd^p for some positive integer p, starting at the x-axis).

%C Also 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 no pyramids of the second kind (a pyramid of the second kind is a sequence U^pd^(2p) for some positive integer p, starting at the x-axis). Column 0 of A108451.

%H Vaclav Kotesovec, <a href="/A108452/b108452.txt">Table of n, a(n) for n = 0..100</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-z)/[1-z(1-z)A(1+A)], where A=1+zA^2+zA^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 From _Vaclav Kotesovec_, Mar 18 2014: (Start)

%F G.f. y(x) satisfies: -1 + 3*x - 3*x^2 + x^3 + y - 3*x^2*y + 2*x^3*y - 3*x*y^2 + 4*x^2*y^2 - 2*x^3*y^2 + x^4*y^2 - x*y^3 + 5*x^2*y^3 - 5*x^3*y^3 + 2*x^4*y^3 = 0

%F a(n) ~ (11+5*sqrt(5))^n * sqrt(247+603/sqrt(5)) / (5*sqrt(Pi)*n^(3/2) *2^(n+7/2))

%F Recurrence: n*(2*n + 1)*(6050*n^7 - 126115*n^6 + 1112432*n^5 - 5378320*n^4 + 15373805*n^3 - 25927435*n^2 + 23799813*n - 9117270)*a(n) = (193600*n^9 - 4138530*n^8 + 37940769*n^7 - 194878383*n^6 + 614482575*n^5 - 1224753180*n^4 + 1530842816*n^3 - 1150685847*n^2 + 475947900*n - 86751000)*a(n-1) - 2*(356950*n^9 - 7743285*n^8 + 72449748*n^7 - 382786506*n^6 + 1254763140*n^5 - 2635287165*n^4 + 3523007792*n^3 - 2857685139*n^2 + 1247080365*n - 211094100)*a(n-2) + (629200*n^9 - 13618110*n^8 + 127285773*n^7 - 672901416*n^6 + 2211415230*n^5 - 4666850055*n^4 + 6281980307*n^3 - 5134608429*n^2 + 2249815860*n - 375921000)*a(n-3) - (205700*n^9 - 4402860*n^8 + 40747203*n^7 - 213640971*n^6 + 697768275*n^5 - 1466844360*n^4 + 1971190342*n^3 - 1610202339*n^2 + 703447650*n - 115668000)*a(n-4) - 2*(n-5)*(2*n - 9)*(6050*n^7 - 83765*n^6 + 482792*n^5 - 1496135*n^4 + 2674295*n^3 - 2716295*n^2 + 1400898*n - 257040)*a(n-5)

%F (End)

%F D-finite with recurrence +n*(2*n+1)*(72425*n-317734)*a(n) +(-3140100*n^3+18675553*n^2-20491436*n+6673146)*a(n-1) +(22916600*n^3-190703953*n^2+432061605*n-302985732)*a(n-2) +2*(-37979850*n^3+409247558*n^2-1317355900*n+1324935945)*a(n-3) +3*(41724600*n^3-547102003*n^2+2263591341*n-2982348982)*a(n-4) +3*(-36023800*n^3+545643269*n^2-2684061391*n+4314486328)*a(n-5) +(46638250*n^3-790948395*n^2+4390868696*n-7976355570)*a(n-6) +(-6636700*n^3+127715416*n^2-812847607*n+1708833588)*a(n-7) -2*(266400*n-1297177)*(2*n-15)*(n-8)*a(n-8)=0. - _R. J. Mathar_, Jul 26 2022

%e a(2)=6 because the paths uUddd, UddUdd, Ududd, UdUddd, Uuddd and UUdddd have no pyramids of the first kind.

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

%o (PARI) {a(n)=local(y=1+x); for(i=1, n, y = -(-1 + 3*x - 3*x^2 + x^3 - 3*x^2*y + 2*x^3*y - 3*x*y^2 + 4*x^2*y^2 - 2*x^3*y^2 + x^4*y^2 - x*y^3 + 5*x^2*y^3 - 5*x^3*y^3 + 2*x^4*y^3) + (O(x^n))^4); polcoeff(y, n)}

%o for(n=0, 20, print1(a(n), ", ")) \\ _Vaclav Kotesovec_, Mar 18 2014

%Y Cf. A027307, A108451, A108449, A108445.

%K nonn

%O 0,3

%A _Emeric Deutsch_, Jun 11 2005