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
A368028 Square array read by antidiagonals; T(n,k) = number of ways a vehicle with capacity k can transport n distinct individuals with distinct starting and finishing points.
1, 0, 1, 0, 1, 1, 0, 2, 1, 1, 0, 6, 6, 1, 1, 0, 24, 54, 6, 1, 1, 0, 120, 648, 90, 6, 1, 1, 0, 720, 9720, 1944, 90, 6, 1, 1, 0, 5040, 174960, 52920, 2520, 90, 6, 1, 1, 0, 40320, 3674160, 1730160, 99000, 2520, 90, 6, 1, 1, 0, 362880, 88179840, 65998800, 4806000, 113400, 2520, 90, 6, 1, 1, 0, 3628800, 2380855680, 2877275520, 274050000, 6966000, 113400, 2520, 90, 6, 1, 1
Offset: 0
Examples
T(3,2)=54 represented by the nine patterns AABBCC, AABCBC, AABCCB, ABABCC, ABACBC, ABACCB, ABBACC, ABBCAC, ABBCCA multiplied by 3!=6 for the permutations of A,B,C; but for example ABCABC would not work as the vehicle would be over its capacity of 2 after picking up 3 passengers.
Links
- math.stackexchange, Passenger entrance/exit combinations
Crossrefs
Formula
If f(n,k,c)=n*f(n-1,k,c+1)+c*f(n,k,c-1) with f(n,k,c)=0 when n<0 or k<0 or c<0 or k
Comments
Examples
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, ...Links
Crossrefs
Programs
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] 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 *)