

A321535


Number of different ways a grasshopper can take n hops without landing on the same point more than once.


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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 nth step has length n.


LINKS

Table of n, a(n) for n=0..42.


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()(pk, k)); f[p]=0; z))); recurse(1, 0)}


CROSSREFS

Cf. A141000, A141002, A175941.
Sequence in context: A240077 A237997 A317885 * A108809 A276846 A303665
Adjacent sequences: A321532 A321533 A321534 * A321536 A321537 A321538


KEYWORD

nonn


AUTHOR

Andrew Howroyd, Nov 12 2018


STATUS

approved



