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