login
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.
14

%I #27 Jul 22 2021 15:18:55

%S 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,

%T 40,47,20,1,1,1,7,31,81,136,125,35,1,1,1,8,43,146,325,496,333,70,1,1,

%U 1,9,57,241,686,1433,1753,939,126,1,1,1,10,73,372,1315,3476,6473,6256,2597,252,1

%N 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.

%H Alois P. Heinz, <a href="/A335570/b335570.txt">Antidiagonals n = 0..60, flattened</a>

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

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

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 1, 1, 1, 1, 1, 1, 1, 1, ...

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

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

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

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

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

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

%e ...

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

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

%p end:

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

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

%t 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]}]];

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

%t Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 12}] // Flatten (* _Jean-François Alcover_, Jan 29 2021, after _Alois P. Heinz_ *)

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

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

%Y Main diagonal gives A335588.

%Y Cf. A340591.

%K nonn,tabl,walk

%O 0,9

%A _Alois P. Heinz_, Jan 26 2021