A149424 -id:A149424

Search: a149424 -id:a149424

Displaying 1-2 of 2 results found.

page 1

A335570

Number A(n,k) of n-step k-dimensional nonnegative lattice walks starting at the origin and using steps that increment all components or decrement one component by 1; square array A(n,k), n>=0, k>=0, read by antidiagonals.

+10
14

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 3, 1, 1, 1, 4, 7, 6, 1, 1, 1, 5, 13, 17, 10, 1, 1, 1, 6, 21, 40, 47, 20, 1, 1, 1, 7, 31, 81, 136, 125, 35, 1, 1, 1, 8, 43, 146, 325, 496, 333, 70, 1, 1, 1, 9, 57, 241, 686, 1433, 1753, 939, 126, 1, 1, 1, 10, 73, 372, 1315, 3476, 6473, 6256, 2597, 252, 1

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

0,9

LINKS

Alois P. Heinz, Antidiagonals n = 0..60, flattened

FORMULA

A(n,k) == 1 (mod k) for k >= 2.

EXAMPLE

A(2,2) = 3: [(0,0),(1,1),(2,2)], [(0,0),(1,1),(0,1)], [(0,0),(1,1),(1,0)].

Square array A(n,k) begins:

1, 1, 1, 1, 1, 1, 1, 1, ...

1, 2, 3, 4, 5, 6, 7, 8, ...

1, 3, 7, 13, 21, 31, 43, 57, ...

1, 6, 17, 40, 81, 146, 241, 372, ...

1, 10, 47, 136, 325, 686, 1315, 2332, ...

1, 20, 125, 496, 1433, 3476, 7525, 14960, ...

1, 35, 333, 1753, 6473, 18711, 46165, 102173, ...

...

MAPLE

b:= proc(n, l) option remember; `if`(n=0, 1, b(n-1, map(x-> x+1, l))+add(

`if`(l[i]>0, b(n-1, sort(subsop(i=l[i]-1, l))), 0), i=1..nops(l)))

end:

A:= (n, k)-> b(n, [0$k]):

seq(seq(A(n, d-n), n=0..d), d=0..12);

MATHEMATICA

b[n_, l_] := b[n, l] = If[n == 0, 1, b[n - 1, l + 1] + Sum[If[l[[i]] > 0, b[n - 1, Sort[ReplacePart[l, i -> l[[i]] - 1]]], 0], {i, 1, Length[l]}]];

A[n_, k_] := b[n, Table[0, {k}]];

Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Jan 29 2021, after Alois P. Heinz *)

CROSSREFS

Columns k=0-10 give: A000012, A001405, A151265, A149424, A346225, A346226, A346227, A346228, A346229, A346230, A346231.

Rows n=0+1,2-3 give: A000012, A000027(k+1), A002061(k+1).

Main diagonal gives A335588.

Cf. A340591.

KEYWORD

nonn,tabl,walk

AUTHOR

Alois P. Heinz, Jan 26 2021

STATUS

approved

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.

+10
2

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

(list; graph; refs; listen; history; text; internal format)

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.

KEYWORD

nonn,walk

AUTHOR

Daniel Carter, Jan 10 2021

STATUS

approved

page 1

Search completed in 0.037 seconds