OFFSET
1,3
COMMENTS
The point is, we are counting permutations of [n] = {1,2,...,n} with the restriction that i cannot move by more than k places. Hence the phrase "permutations with restricted displacements". - N. J. A. Sloane, Mar 07 2014
The triangle could have been defined as an infinite square array by setting a(n,k) = n! for k >= n.
REFERENCES
H. Minc, Permanents, Encyc. Math. #6, 1978, p. 48
LINKS
Alois P. Heinz, Rows n = 1..23, flattened
Henry Beker and Chris Mitchell, Permutations with restricted displacement, SIAM J. Algebraic Discrete Methods 8 (1987), no. 3, 338--363. MR0897734 (89f:05009)
N. S. Mendelsohn, Permutations with confined displacement, Canad. Math. Bull., 4 (1961), 29-38.
N. Metropolis, M. L. Stein, P. R. Stein, Permanents of cyclic (0,1) matrices, J. Combin. Theory, 7 (1969), 291-321.
Wikipedia, Permanent (mathematics)
FORMULA
a(n,k) = per(sum(P^j, j=0..k-1)), where P is n X n, P[ i, i+1 (mod n) ]=1, 0's otherwise.
a(n,n) - a(n,n-1) = A002467(n). - Alois P. Heinz, Mar 06 2019
EXAMPLE
a(4,3) = 9 because 9 permutations of {1,2,3,4} are allowed if each i can be placed on 3 positions i+0, i+1, i+2 (mod 4): 1234, 1423, 1432, 3124, 3214, 3412, 4123, 4132, 4213.
Triangle begins:
1,
1, 2,
1, 2, 6,
1, 2, 9, 24,
1, 2, 13, 44, 120,
1, 2, 20, 80, 265, 720,
1, 2, 31, 144, 579, 1854, 5040,
1, 2, 49, 264, 1265, 4738, 14833, 40320,
1, 2, 78, 484, 2783, 12072, 43387, 133496, 362880,
1, 2, 125, 888, 6208, 30818, 126565, 439792, 1334961, 3628800,
...
MAPLE
with(LinearAlgebra):
a:= (n, k)-> Permanent(Matrix(n,
(i, j)-> `if`(0<=j-i and j-i<k or j-i<k-n, 1, 0))):
seq(seq(a(n, k), k=1..n), n=1..10);
MATHEMATICA
a[n_, k_] := Permanent[Table[If[0 <= j-i && j-i < k || j-i < k-n, 1, 0], {i, 1, n}, {j, 1, n}]]; Table[Table[a[n, k], {k, 1, n}], {n, 1, 10}] // Flatten (* Jean-François Alcover, Mar 10 2014, after Alois P. Heinz *)
CROSSREFS
a(n,ceiling(n/2)) gives A306738.
KEYWORD
nonn,tabl
AUTHOR
EXTENSIONS
Comments and more terms from Len Smiley
More terms from Vladeta Jovovic, Oct 02 2003
Edited by Alois P. Heinz, Dec 18 2010
STATUS
approved