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

Author

Alois P. Heinz, Jan 26 2021

Keywords

• nonn
• tabl
• walk

Examples

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

Links

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

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.

Programs

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 *)

Formula

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