%I #9 Nov 17 2018 21:12:51

%S 1,1,1,1,2,3,4,7,9,14,23,35,56,86,136,216,338,535,848,1374,2234,3594,

%T 5750,9265,14856,24019,39350,64222,104878,170247,276489,452138,739486,

%U 1207429,1974247,3234889,5295560,8708262,14276970,23493811,38683402,63773042,104840427

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

%C 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.

%C In other words, the number of n step self avoiding walks on a line where the n-th step has length n.

%e a(6) = 4 because there are 4 walks with 6 steps:

%e 0 -> 1 -> 3 -> 6 -> 2 -> 7 -> 13,

%e 0 -> 1 -> 3 -> 6 -> 10 -> 5 -> 11,

%e 0 -> 1 -> 3 -> 6 -> 10 -> 15 -> 9,

%e 0 -> 1 -> 3 -> 6 -> 10 -> 15 -> 21.

%o (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)}

%Y Cf. A141000, A141002, A175941.

%K nonn

%O 0,5

%A _Andrew Howroyd_, Nov 12 2018