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.

1, 6, 288, 24444, 2738592, 361998432, 53414223552, 8525232846072, 1443209364298944, 255769050813120576, 47020653859202576640, 8907614785269428079168, 1730208409741026141405696, 343266632435192859791576064, 69350551439109880798294334208

Offset

0,2

Comments

There are no such walks with length that is not a multiple of 4.

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.

The analogous problem in dimensions 1 and 2 are given respectively by A000108 (the Catalan numbers) and A006335.

No closed form is known. In fact, it is not known whether this sequence is D-finite (see Bacher et al.).

Links

Alois P. Heinz, Table of n, a(n) for n = 0..150

Axel Bacher, Manuel Kauers, and Rika Yatchak, Continued Classification of 3D Lattice Walks in the Positive Octant, arXiv:1511.05763 [math.CO], 2015.

Maple

b:= proc(n, l) option remember; `if`(n=0, 1, `if`(add(i, i=l)+3<n,
      b(n-1, map(x-> x+1, l)), 0) +add(`if`(l[i]>0,
      b(n-1, sort(subsop(i=l[i]-1, l))), 0), i=1..3))
    end:
a:= n-> b(4*n, [0$3]):
seq(a(n), n=0..15);  # Alois P. Heinz, Jan 12 2021

Mathematica

b[n_, l_] := b[n, l] = If[n == 0, 1, If[Total[l] + 3 < n,
  b[n-1, l+1]], 0] + Sum[If[l[[i]] > 0,
  b[n-1, Sort[ReplacePart[l, i -> l[[i]]-1]]], 0], {i, 1, 3}] /. Null -> 0;
a[n_] := b[4n, {0, 0, 0}];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Jul 10 2021, after Alois P. Heinz *)

Prog

(Python)
import itertools as it
i = 0
while 1:
    counts = {(a, b, c):0 for a, b, c in it.product(range(i+1), repeat=3)}
    counts[0, 0, 0] = 1
    for _ in range(4*i):
        update = {(a, b, c):0 for a, b, c in it.product(range(i+1), repeat=3)}
        for x, y, z in counts:
            if counts[x, y, z] != 0:
                for coord in [(x+1, y+1, z+1), (x-1, y, z), (x, y-1, z), (x, y, z-1)]:
                    if coord in update:
                        update[coord] += counts[x, y, z]
        counts = update
    print(i, counts[0, 0, 0])
    i += 1

Crossrefs

Cf. A000108, A006335, A149424.

Column k=3 of A340591.

Sequence in context: A172660 A203051 A128792 * A027875 A203422 A042119

Adjacent sequences: A340537 A340538 A340539 * A340541 A340542 A340543

Keyword

nonn,walk

Author

Daniel Carter, Jan 10 2021

Status

approved