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

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.

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()(p-k, 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