A316674 Number A(n,k) of paths from {0}^k to {n}^k that always move closer to {n}^k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 3, 2, 1, 1, 13, 26, 4, 1, 1, 75, 818, 252, 8, 1, 1, 541, 47834, 64324, 2568, 16, 1, 1, 4683, 4488722, 42725052, 5592968, 26928, 32, 1, 1, 47293, 617364026, 58555826884, 44418808968, 515092048, 287648, 64, 1

Offset: 0

Author

Alois P. Heinz, Jul 10 2018

Keywords

• nonn
• tabl
• walk

Comments

A(n,k) is the number of nonnegative integer matrices with k columns and any number of nonzero rows with column sums n. - Andrew Howroyd, Jan 23 2020

Examples

			Square array A(n,k) begins:
  1,  1,     1,         1,              1,                    1, ...
  1,  1,     3,        13,             75,                  541, ...
  1,  2,    26,       818,          47834,              4488722, ...
  1,  4,   252,     64324,       42725052,          58555826884, ...
  1,  8,  2568,   5592968,    44418808968,      936239675880968, ...
  1, 16, 26928, 515092048, 50363651248560, 16811849850663255376, ...
		

Links

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

Crossrefs

Columns k=0..3 give: A000012, A011782, A052141, A316673.

Rows n=0..2 give: A000012, A000670, A059516.

Main diagonal gives A316677.

Cf. A011782, A219727, A262809, A331315, A331485, A331636.

Programs

Maple

A:= (n, k)-> `if`(k=0, 1, ceil(2^(n-1))*add(add((-1)^i*
     binomial(j, i)*binomial(j-i, n)^k, i=0..j), j=0..k*n)):
seq(seq(A(n, d-n), n=0..d), d=0..10);

Mathematica

A[n_, k_] := Sum[If[k == 0, 1, Binomial[j+n-1, n]^k] Sum[(-1)^(i-j)* Binomial[i, j], {i, j, n k}], {j, 0, n k}];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Nov 04 2021 *)

PARI

T(n,k)={my(m=n*k); sum(j=0, m, binomial(j+n-1,n)^k*sum(i=j, m, (-1)^(i-j)*binomial(i, j)))} \\ Andrew Howroyd, Jan 23 2020

Formula

A(n,k) = A262809(n,k) * A011782(n) for k>0, A(n,0) = 1.

A(n,k) = Sum_{j=0..n*k} binomial(j+n-1,n)^k * Sum_{i=j..n*k} (-1)^(i-j) * binomial(i,j). - Andrew Howroyd, Jan 23 2020