login
A321535
Number of different ways a grasshopper can take n hops without landing on the same point more than once.
2
1, 1, 1, 1, 2, 3, 4, 7, 9, 14, 23, 35, 56, 86, 136, 216, 338, 535, 848, 1374, 2234, 3594, 5750, 9265, 14856, 24019, 39350, 64222, 104878, 170247, 276489, 452138, 739486, 1207429, 1974247, 3234889, 5295560, 8708262, 14276970, 23493811, 38683402, 63773042, 104840427
OFFSET
0,5
COMMENTS
Consider a grasshopper (cf. A141000, A141002) that starts at x=0 at time 0, then makes successive hops of sizes 1, 2, 3, ..., n, subject to the constraints that it must always land on a point x >= 0 and no point may be visited more than once; sequence gives number of different ways that it can make n hops.
In other words, the number of n step self avoiding walks on a line where the n-th step has length n.
EXAMPLE
a(6) = 4 because there are 4 walks with 6 steps:
0 -> 1 -> 3 -> 6 -> 2 -> 7 -> 13,
0 -> 1 -> 3 -> 6 -> 10 -> 5 -> 11,
0 -> 1 -> 3 -> 6 -> 10 -> 15 -> 9,
0 -> 1 -> 3 -> 6 -> 10 -> 15 -> 21.
PROG
(PARI) a(n)={local(f=vectorsmall(n*(n+1)/2+1)); my(recurse(p, k)=if(p>0&&!f[p], if(k==n, 1, f[p]=1; k++; my(z=self()(p+k, k) + self()(p-k, k)); f[p]=0; z))); recurse(1, 0)}
CROSSREFS
KEYWORD
nonn
AUTHOR
Andrew Howroyd, Nov 12 2018
STATUS
approved