A229142 Number A(n,k) of lattice paths from {n}^k to {0}^k using steps that decrement one component or all components by 1; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 3, 1, 1, 1, 7, 13, 1, 1, 1, 25, 115, 63, 1, 1, 1, 121, 2641, 2371, 321, 1, 1, 1, 721, 114121, 392641, 54091, 1683, 1, 1, 1, 5041, 7489441, 169417921, 67982041, 1307377, 8989, 1, 1, 1, 40321, 681120721, 137322405361, 308238414121, 12838867105, 32803219, 48639, 1, 1

Offset: 0

Author

Alois P. Heinz, Sep 23 2013

Keywords

• nonn
• tabl

Comments

Column k is the diagonal of the rational function 1 / (1 - Sum_{j=1..k} x_j - Product_{j=1..k} x_j) for k>1. - Seiichi Manyama, Jul 10 2020

Examples

			A(1,3) = 3*2+1 = 7:
          (0,1,1)-(0,0,1)
         /       X       \
  (1,1,1)-(1,0,1) (0,1,0)-(0,0,0)
       \ \       X       / /
        \ (1,1,0)-(1,0,0) /
         `---------------´
Square array A(n,k) begins:
  1, 1,    1,       1,           1,               1, ...
  1, 1,    3,       7,          25,             121, ...
  1, 1,   13,     115,        2641,          114121, ...
  1, 1,   63,    2371,      392641,       169417921, ...
  1, 1,  321,   54091,    67982041,    308238414121, ...
  1, 1, 1683, 1307377, 12838867105, 629799991355641, ...
		

Links

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

Crossrefs

Columns k=0+1, 2-10 give: A000012, A001850, A081798, A082488, A082489, A229049, A229674, A229675, A229676, A229677.

Rows n=0-1 give: A000012, A038507 (for k>1).

Main diagonal gives: A229267.

Cf. A060854, A227578, A227655, A225094, A210472, A262809, A263159.

Programs

Maple

with(combinat):
A:= (n,k)-> `if`(k<2, 1, add(multinomial(n+(k-1)*j, n-j, j$k), j=0..n)):
seq(seq(A(n, d-n), n=0..d), d=0..10);

Mathematica

a[, 0] = a[, 1] = 1; a[n_, k_] := Sum[Product[Binomial[n+j*m, m], {j, 0, k-1}], {m, 0, n}]; Table[a[n-k, k], {n, 0, 10}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Dec 11 2013 *)

Formula

A(n,k) = Sum_{j=0..n} multinomial(n+(k-1)*j; n-j, {j}^k) for k>1, A(n,0) = A(n,1) = 1.

G.f. of column k: Sum_{j>=0} (k*j)!/j!^k * x^j / (1-x)^(k*j+1). for k>1. - Seiichi Manyama, Jul 10 2020