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

%I #75 Apr 22 2019 01:14:30

%S 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,

%T 1854,5040,1,2,49,264,1265,4738,14833,40320,1,2,78,484,2783,12072,

%U 43387,133496,362880,1,2,125,888,6208,30818,126565,439792,1334961,3628800

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

%C 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

%C The triangle could have been defined as an infinite square array by setting a(n,k) = n! for k >= n.

%D H. Minc, Permanents, Encyc. Math. #6, 1978, p. 48

%H Alois P. Heinz, <a href="/A008305/b008305.txt">Rows n = 1..23, flattened</a>

%H Henry Beker and Chris Mitchell, <a href="http://dx.doi.org/10.1137/0608029">Permutations with restricted displacement</a>, SIAM J. Algebraic Discrete Methods 8 (1987), no. 3, 338--363. MR0897734 (89f:05009)

%H N. S. Mendelsohn, <a href="http://dx.doi.org/10.4153/CMB-1961-005-4">Permutations with confined displacement</a>, Canad. Math. Bull., 4 (1961), 29-38.

%H N. Metropolis, M. L. Stein, P. R. Stein, <a href="http://dx.doi.org/10.1016/S0021-9800(69)80058-X">Permanents of cyclic (0,1) matrices</a>, J. Combin. Theory, 7 (1969), 291-321.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Permanent_(mathematics)">Permanent (mathematics)</a>

%F 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.

%F a(n,n) - a(n,n-1) = A002467(n). - _Alois P. Heinz_, Mar 06 2019

%e 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.

%e Triangle begins:

%e 1,

%e 1, 2,

%e 1, 2, 6,

%e 1, 2, 9, 24,

%e 1, 2, 13, 44, 120,

%e 1, 2, 20, 80, 265, 720,

%e 1, 2, 31, 144, 579, 1854, 5040,

%e 1, 2, 49, 264, 1265, 4738, 14833, 40320,

%e 1, 2, 78, 484, 2783, 12072, 43387, 133496, 362880,

%e 1, 2, 125, 888, 6208, 30818, 126565, 439792, 1334961, 3628800,

%e ...

%p with(LinearAlgebra):

%p a:= (n, k)-> Permanent(Matrix(n,

%p (i, j)-> `if`(0<=j-i and j-i<k or j-i<k-n, 1, 0))):

%p seq(seq(a(n, k), k=1..n), n=1..10);

%t 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_ *)

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

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

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

%Y Cf. A002467, A306714.

%K nonn,tabl

%O 1,3

%A _N. J. A. Sloane_

%E Comments and more terms from _Len Smiley_

%E More terms from _Vladeta Jovovic_, Oct 02 2003

%E Edited by _Alois P. Heinz_, Dec 18 2010