A108452 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).
1, 1, 6, 44, 344, 2856, 24816, 223016, 2056256, 19344472, 184956240, 1792088296, 17558218048, 173659691928, 1731556718224, 17387182158184, 175670235597120, 1784561125349464, 18216639085961552, 186762117058304104
Offset: 0
Keywords
Examples
a(2)=6 because the paths uUddd, UddUdd, Ududd, UdUddd, Uuddd and UUdddd have no pyramids of the first kind.
Links
- Vaclav Kotesovec, Table of n, a(n) for n = 0..100
- Emeric Deutsch, Problem 10658: Another Type of Lattice Path, American Math. Monthly, 107, 2000, 368-370.
Programs
-
Maple
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);
-
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)} for(n=0, 20, print1(a(n), ", ")) \\ Vaclav Kotesovec, Mar 18 2014
Formula
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).
From Vaclav Kotesovec, Mar 18 2014: (Start)
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
a(n) ~ (11+5*sqrt(5))^n * sqrt(247+603/sqrt(5)) / (5*sqrt(Pi)*n^(3/2) *2^(n+7/2))
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)
(End)
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
Comments