cp's OEIS Frontend

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

%I A321535 #9 Nov 17 2018 21:12:51
%S A321535 1,1,1,1,2,3,4,7,9,14,23,35,56,86,136,216,338,535,848,1374,2234,3594,
%T A321535 5750,9265,14856,24019,39350,64222,104878,170247,276489,452138,739486,
%U A321535 1207429,1974247,3234889,5295560,8708262,14276970,23493811,38683402,63773042,104840427
%N A321535 Number of different ways a grasshopper can take n hops without landing on the same point more than once.
%C A321535 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 A321535 In other words, the number of n step self avoiding walks on a line where the n-th step has length n.
%e A321535 a(6) = 4 because there are 4 walks with 6 steps:
%e A321535 0 -> 1 -> 3 -> 6 -> 2 -> 7 -> 13,
%e A321535 0 -> 1 -> 3 -> 6 -> 10 -> 5 -> 11,
%e A321535 0 -> 1 -> 3 -> 6 -> 10 -> 15 -> 9,
%e A321535 0 -> 1 -> 3 -> 6 -> 10 -> 15 -> 21.
%o A321535 (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 A321535 Cf. A141000, A141002, A175941.
%K A321535 nonn
%O A321535 0,5
%A A321535 _Andrew Howroyd_, Nov 12 2018