login
Number of n-step walks on cubic lattice starting at (0,0,0), ending at (floor(n/3), floor((n+1)/3), floor((n+2)/3)), remaining in the first (nonnegative) octant and using steps (0,0,1), (0,1,0), (1,0,0), (-1,1,1), (1,-1,1), and (1,1,-1).
3

%I #25 May 12 2020 11:50:44

%S 1,1,3,12,41,179,909,3968,19680,106368,516905,2717631,15139485,

%T 77813569,422589823,2395441908,12734635078,70577595746,404540380566,

%U 2199035619696,12356298623126,71368686011040,394076753535029,2236273925952447,12988459939106601

%N Number of n-step walks on cubic lattice starting at (0,0,0), ending at (floor(n/3), floor((n+1)/3), floor((n+2)/3)), remaining in the first (nonnegative) octant and using steps (0,0,1), (0,1,0), (1,0,0), (-1,1,1), (1,-1,1), and (1,1,-1).

%H Alois P. Heinz, <a href="/A328299/b328299.txt">Table of n, a(n) for n = 0..1039</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path">Lattice path</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Self-avoiding_walk">Self-avoiding walk</a>

%e a(2) = 3: [(0,0,0),(1,0,0),(0,1,1)], [(0,0,0),(0,1,0),(0,1,1)], [(0,0,0),(0,0,1),(0,1,1)].

%p b:= proc(l) option remember; `if`(l[-1]=0, 1, (r-> add(

%p add(add(`if`(i+j+k=1, (h-> `if`(h[1]<0, 0, b(h)))(

%p sort(l-[i, j, k])), 0), k=r), j=r), i=r))([$-1..1]))

%p end:

%p a:= n-> b([floor((n+i)/3)$i=0..2]):

%p seq(a(n), n=0..24);

%t b[l_] := b[l] = If[Last[l] == 0, 1, Sum[If[i + j + k == 1, Function[h, If[h[[1]] < 0, 0, b[h]]][Sort[l - {i, j, k}]], 0], {i, {-1, 0, 1}}, {j, {-1, 0, 1}}, {k, {-1, 0, 1}}]];

%t a[n_] := b[Table[Floor[(n+i)/3], {i, 0, 2}]];

%t a /@ Range[0, 24] (* _Jean-François Alcover_, May 12 2020, after Maple *)

%Y Cf. A006472, A022916, A328297, A328345.

%K nonn,walk

%O 0,3

%A _Alois P. Heinz_, Oct 11 2019