A008305 Triangle read by rows: a(n,k) = number of permutations of [n] allowing i->i+j (mod n), j=0..k-1.

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

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

Diagonals (from the right): A000142, A000166, A000179, A000183, A004307, A189389, A184965.

Diagonals (from the left): A000211 or A048162, 4*A000382 or A004306 or A000803, A000804, A000805.

a(n,ceiling(n/2)) gives A306738.

Cf. A002467, A306714.

Sequence in context: A208757 A361830 A133643 * A208763 A355721 A249027

Adjacent sequences: A008302 A008303 A008304 * A008306 A008307 A008308

Keyword

nonn,tabl

Author

N. J. A. Sloane

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