cp's OEIS Frontend

A340540 Number of walks of length 4n in the first octant using steps (1,1,1), (-1,0,0), (0,-1,0), and (0,0,-1) that start and end at the origin.

%I A340540 #17 Jul 10 2021 16:22:21
%S A340540 1,6,288,24444,2738592,361998432,53414223552,8525232846072,
%T A340540 1443209364298944,255769050813120576,47020653859202576640,
%U A340540 8907614785269428079168,1730208409741026141405696,343266632435192859791576064,69350551439109880798294334208
%N A340540 Number of walks of length 4n in the first octant using steps (1,1,1), (-1,0,0), (0,-1,0), and (0,0,-1) that start and end at the origin.
%C A340540 There are no such walks with length that is not a multiple of 4.
%C A340540 a(n) is also the number of arrangements of n copies each of "a", "b", "c", and "d" such that no prefix has more b's, c's, or d's than a's.
%C A340540 The analogous problem in dimensions 1 and 2 are given respectively by A000108 (the Catalan numbers) and A006335.
%C A340540 No closed form is known. In fact, it is not known whether this sequence is D-finite (see Bacher et al.).
%H A340540 Alois P. Heinz, <a href="/A340540/b340540.txt">Table of n, a(n) for n = 0..150</a>
%H A340540 Axel Bacher, Manuel Kauers, and Rika Yatchak, <a href="https://arxiv.org/abs/1511.05763">Continued Classification of 3D Lattice Walks in the Positive Octant</a>, arXiv:1511.05763 [math.CO], 2015.
%p A340540 b:= proc(n, l) option remember; `if`(n=0, 1, `if`(add(i, i=l)+3<n,
%p A340540       b(n-1, map(x-> x+1, l)), 0) +add(`if`(l[i]>0,
%p A340540       b(n-1, sort(subsop(i=l[i]-1, l))), 0), i=1..3))
%p A340540     end:
%p A340540 a:= n-> b(4*n, [0$3]):
%p A340540 seq(a(n), n=0..15);  # _Alois P. Heinz_, Jan 12 2021
%t A340540 b[n_, l_] := b[n, l] = If[n == 0, 1, If[Total[l] + 3 < n,
%t A340540   b[n-1, l+1]], 0] + Sum[If[l[[i]] > 0,
%t A340540   b[n-1, Sort[ReplacePart[l, i -> l[[i]]-1]]], 0], {i, 1, 3}] /. Null -> 0;
%t A340540 a[n_] := b[4n, {0, 0, 0}];
%t A340540 Table[a[n], {n, 0, 15}] (* _Jean-François Alcover_, Jul 10 2021, after _Alois P. Heinz_ *)
%o A340540 (Python)
%o A340540 import itertools as it
%o A340540 i = 0
%o A340540 while 1:
%o A340540     counts = {(a,b,c):0 for a,b,c in it.product(range(i+1), repeat=3)}
%o A340540     counts[0,0,0] = 1
%o A340540     for _ in range(4*i):
%o A340540         update = {(a,b,c):0 for a,b,c in it.product(range(i+1), repeat=3)}
%o A340540         for x,y,z in counts:
%o A340540             if counts[x,y,z] != 0:
%o A340540                 for coord in [(x+1,y+1,z+1), (x-1,y,z), (x,y-1,z), (x,y,z-1)]:
%o A340540                     if coord in update:
%o A340540                         update[coord] += counts[x,y,z]
%o A340540         counts = update
%o A340540     print(i, counts[0,0,0])
%o A340540     i += 1
%Y A340540 Cf. A000108, A006335, A149424.
%Y A340540 Column k=3 of A340591.
%K A340540 nonn,walk
%O A340540 0,2
%A A340540 _Daniel Carter_, Jan 10 2021