A189389 -id:A189389 - cp's OEIS frontend

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

N. J. A. Sloane

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.

			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,
  ...

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

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)

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.

with(LinearAlgebra):
a:= (n, k)-> Permanent(Matrix(n,
             (i, j)-> `if`(0<=j-i and j-i

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 *)

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

Comments and more terms from Len Smiley
More terms from Vladeta Jovovic, Oct 02 2003
Edited by Alois P. Heinz, Dec 18 2010

A321352 Triangle T(n,k) giving the number of permutations pi of {1,2,...,n} such that for all i, pi(i) is not in {i, i+1, ..., i+k-1} (mod n), with 0 <= k <= n - 1.

Original entry on oeis.org

1, 2, 1, 6, 2, 1, 24, 9, 2, 1, 120, 44, 13, 2, 1, 720, 265, 80, 20, 2, 1, 5040, 1854, 579, 144, 31, 2, 1, 40320, 14833, 4738, 1265, 264, 49, 2, 1, 362880, 133496, 43387, 12072, 2783, 484, 78, 2, 1, 3628800, 1334961, 439792, 126565, 30818, 6208, 888, 125, 2, 1

Offset: 1

Peter Kagey, Feb 25 2020

This is A008305 with the rows reversed.
First column is A000142 (factorial numbers).
Second column is A000166 (derangements).
Third column is A000179 (ménage numbers).
Fourth column is A000183 (discordant permutations)

			Table begins:
       1
       2,      1
       6,      2,     1
      24,      9,     2,     1
     120,     44,    13,     2,    1
     720,    265,    80,    20,    2,   1
    5040,   1854,   579,   144,   31,   2,  1
   40320,  14833,  4738,  1265,  264,  49,  2, 1
  362880, 133496, 43387, 12072, 2783, 484, 78, 2, 1

Peter Kagey, Table of n, a(n) for n = 1..276 (first 23 rows, flattened)

Cf. A008305.

Cf. A000142, A000166, A000179, A000183, A004307, A189389, A184965.

A324624 Number of permutations p of [4+n] such that n is the maximum of the number of elements in any integer interval [p(i)..i+(4+n)*[i

Original entry on oeis.org

0, 1, 1, 29, 215, 2299, 24610, 290203, 3664639, 49665695, 719356045, 11100719773, 181925519591, 3157018912485, 57848571473665, 1116400995778789, 22637359008083824, 481232567245746693, 10703530470036896333, 248615220921060645505, 6020095122314424497575

Offset: 0

Alois P. Heinz, Mar 09 2019

nonn

Row n=4 of A324563 and column of A324564 (as array).

Cf. A004307, A189389.

a(n) = A004307(n+4) - A189389(n+4).

A324625 Number of permutations p of [5+n] such that n is the maximum of the number of elements in any integer interval [p(i)..i+(5+n)*[i

Original entry on oeis.org

0, 1, 1, 47, 406, 5320, 65209, 876865, 12428079, 187013213, 2977639454, 50100075551, 889030153223, 16605705694513, 325842147818131, 6704025812865230, 144359437306938642, 3247712172059705741, 76210676599647821811, 1862449116865631232577

Offset: 0

Alois P. Heinz, Mar 09 2019

nonn

Row n=5 of A324563 column of A324564 (as array).

Cf. A189389, A184965.

a(n) = A189389(n+5) - A184965(n+5).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A321352 Triangle T(n,k) giving the number of permutations pi of {1,2,...,n} such that for all i, pi(i) is not in {i, i+1, ..., i+k-1} (mod n), with 0 <= k <= n - 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A324624 Number of permutations p of [4+n] such that n is the maximum of the number of elements in any integer interval [p(i)..i+(4+n)*[i

Views

Author

Keywords

Crossrefs

Formula

A324625 Number of permutations p of [5+n] such that n is the maximum of the number of elements in any integer interval [p(i)..i+(5+n)*[i

Views

Author

Keywords

Crossrefs

Formula