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.

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

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,  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.

Sequence in context: A303912 A133815 A305027 * A362644 A323718 A130580

Adjacent sequences: A335567 A335568 A335569 * A335571 A335572 A335573

Keyword

nonn,tabl,walk

Author

Alois P. Heinz, Jan 26 2021

Status

approved