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

1, 1, 1, 1, 1, 1, 1, 2, 0, 1, 1, 6, 2, 0, 1, 1, 24, 54, 2, 0, 1, 1, 120, 1944, 384, 2, 0, 1, 1, 720, 99000, 132000, 2550, 2, 0, 1, 1, 5040, 6966000, 79716000, 8059800, 16506, 2, 0, 1, 1, 40320, 655678800, 78928416000, 57010275000, 471369024, 105840, 2, 0, 1

Offset

0,8

Comments

An interior point p = (p_1, ..., p_k) has k>0 components with 0<p_i<n for 1<=i<=k.

Links

Alois P. Heinz, Antidiagonals n = 0..20, flattened

Example

A(n,0) = 1: [()].
A(0,k) = 1: [{0}^k].
A(1,1) = 1: [(1), (0)].
A(2,1) = 0, there is no path from (2) to (0) without interior points.
A(1,2) = 2: [(1,1), (0,1), (0,0)], [(1,1), (1,0), (0,0)].
A(1,3) = 6: [(1,1,1), (0,1,1), (0,0,1), (0,0,0)], [(1,1,1), (0,1,1), (0,1,0), (0,0,0)], [(1,1,1), (1,0,1), (0,0,1), (0,0,0)], [(1,1,1), (1,0,1), (1,0,0), (0,0,0)], [(1,1,1), (1,1,0), (0,1,0), (0,0,0)], [(1,1,1), (1,1,0), (1,0,0), (0,0,0)].
Square array A(n,k) begins:
  1, 1, 1,     1,         1,              1, ...
  1, 1, 2,     6,        24,            120, ...
  1, 0, 2,    54,      1944,          99000, ...
  1, 0, 2,   384,    132000,       79716000, ...
  1, 0, 2,  2550,   8059800,    57010275000, ...
  1, 0, 2, 16506, 471369024, 38606650125120, ...

Maple

b:= proc(n, l) option remember; local m; m:= nops(l);
      `if`(m=0 or l[m]=0, 1, `if`(l[1]>0 and l[m]<n, 0,
       add(`if`(l[i]=0, 0, b(n, sort(subsop(i=l[i]-1, l)))), i=1..m)))
    end:
A:= (n, k)-> b(n, [n$k]):
seq(seq(A(n, d-n), n=0..d), d=0..10);

Mathematica

b[n_, l_] := b[n, l] = With[{m = Length[l]}, If[m == 0 || l[[m]] == 0, 1, If[l[[1]] > 0 && l[[m]] < n, 0, Sum[If[l[[i]] == 0, 0, b[n, Sort[ReplacePart[l, i -> l[[i]] - 1]]]], {i, 1, m}]]] ]; a[n_, k_] := b[n, Array[n&, k]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 16 2013, translated from Maple *)

Crossrefs

Columns k=0, 2-4 give: A000012, A040000, A060774, A225220.

Rows n=0-4 give: A000012, A000142, A071798(k) (for k>0), A225096, A225221.

Main diagonal gives: A225111.

Cf. A089759 (unrestricted paths), A210472, A262809, A263159.

Sequence in context: A085496 A228748 A343464 * A350594 A295859 A180160

Adjacent sequences: A225091 A225092 A225093 * A225095 A225096 A225097

Keyword

nonn,tabl,walk

Author

Alois P. Heinz, Apr 27 2013

Status

approved