# [seqfan] Re: a new lattice walk

Heinz, Alois alois.heinz at hs-heilbronn.de
Wed May 8 17:51:15 CEST 2013

```There is a recursive formula:

for n>=5:
a(n) =  ((n-1)*(414288-1901580*n+186029*n^6-869551*n^5+2393807*n^4
-3938624*n^3+3753546*n^2+1050*n^8-21605*n^7)*a(n-1)
+(-17751540*n-12215020*n^5+3494038*n^6+3777840+27478070*n^4
-39711374*n^3+35488098*n^2-2700*n^9+62370*n^8-621126*n^7)*a(n-2)
+(-18193248+77490792*n-9138800*n^6+35323128*n^5-88122332*n^4
+141370392*n^3-140075264*n^2+5400*n^9-135540*n^8+1476432*n^7)*a(n-3)
+(-192473328*n+48577536+17091500*n^6-70036368*n^5+184890672*n^4
-313388816*n^3+328043052*n^2-8400*n^9+224440*n^8-2600032*n^7)*a(n-4)
+8*(n-5)*(150*n^6-2015*n^5+10852*n^4-29867*n^3+44208*n^2-33540*n
+10416)*(-9+2*n)^2*a(n-5)) / (n^2*(396988*n-487261*n^2+150*n^7
-3065*n^6+26092*n^5-119602*n^4+317746*n^3-131048))

a(100) = 2551133493215233526810399952776915312761455858624338712449

With regards, Alois

Am 08.05.2013 15:56, schrieb David Scambler:
> I am surprised that superseeker does not find a formula for this deceptively simple scenario.
>
> 2-D lattice walk of length 2n beginning and ending at the origin, using steps in {NSEW} starting with East, then always moving straight ahead or turning left.
>
> 1,0,1,3,9,30,103,357,1257,4494,16246,59246,217719, ...
>
> e.g. n=2 a(2)=1
> ENWS
>
> e.g. n=3 a(3)=3
> EENWWS
> ENNWSS
> ENWWSE
>
> e.g. n=4 a(4) = 9
> EEENWWWS
> EENNWWSS
> EENWWWSE
> ENNNWSSS
> ENNWWSSE
> ENWWWSEE
> ENWWSSEN
> ENWSSENW
> ENWSENWS
>
> Note: paths do not have to be self avoiding.
>
> dave

```