A004307 -id:A004307 - 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

A184965 Number of permutations p of [n] such that (n-p(i)+i) mod n >= 6 for all i.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 0, 1, 2, 78, 888, 13909, 204448, 3182225, 51504968, 873224962, 15498424578, 287972983669, 5598118158336, 113756109812283, 2413723031593090, 53416658591208438, 1231458960862452472, 29538634475147637783, 736321207493996695072

Offset: 0

Alois P. Heinz, Apr 20 2011

nonn

			a(8) = 2: (2,3,4,5,6,7,8,1), (3,4,5,6,7,8,1,2).

Shalosh B. Ekhad and Doron Zeilberger, Table of n, a(n) for n = 0..100
D. Zeilberger, Automatic Enumeration of Generalized Ménage Numbers

A diagonal of A008305.

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

with(LinearAlgebra):
a:= n-> `if`(n=0, 1, Permanent(Matrix(n, (i, j)->
                     `if`(i-j<=0 and i-j>-6 or i-j>n-6, 0, 1)))):
seq(a(n), n=0..15);

a[n_] := Permanent[Table[If[i-j <= 0 && i-j > -6 || i-j > n-6, 0, 1], {i, 1, n}, {j, 1, n}]]; a[0] = 1; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 15}] (* Jean-François Alcover, Jan 07 2016, adapted from Maple *)

A189389 Number of permutations p of [n] such that (n-p(i)+i) mod n >= 5 for all i.

Original entry on oeis.org

1, 0, 0, 0, 0, 0, 1, 2, 49, 484, 6208, 79118, 1081313, 15610304, 238518181, 3850864416, 65598500129, 1177003136892, 22203823852849, 439598257630414, 9117748844458320, 197776095898147080, 4479171132922158213, 105749311074795459594, 2598770324359627927649

Offset: 0

Alois P. Heinz, Apr 20 2011

nonn

			a(7) = 2: (2,3,4,5,6,7,1), (3,4,5,6,7,1,2).

Shalosh B. Ekhad and Doron Zeilberger, Table of n, a(n) for n = 0..100
D. Zeilberger, Automatic Enumeration of Generalized Ménage Numbers

A diagonal of A008305.

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

with(LinearAlgebra):
a:= n-> `if`(n=0, 1, Permanent(Matrix(n, (i, j)->
                     `if`(i-j<=0 and i-j>-5 or i-j>n-5, 0, 1)))):
seq(a(n), n=0..15);

a[n_] := Permanent[Table[If[i-j <= 0 && i-j > -5 || i-j > n-5, 0, 1], {i, 1, n}, {j, 1, n}]]; a[0] = 1; Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Jan 07 2016, adapted from Maple *)

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.

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

Original entry on oeis.org

0, 1, 1, 18, 113, 1001, 9289, 95747, 1075779, 13129188, 173006731, 2449243815, 37082963875, 598045522873, 10236223969309, 185344819109346, 3539853769700281, 71122126197951465, 1499666213536206971, 33113352117542113491, 764116379880803291501

Offset: 0

Alois P. Heinz, Mar 09 2019

nonn

Alois P. Heinz, Table of n, a(n) for n = 0..447

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

Cf. A000183, A004307.

a(n) = A000183(n+3) - A004307(n+3).

A267060 a(n) = number of different ways to seat a set of n married male-female couples at a round table so that men and women alternate and every man is separated by at least d = 2 men from his wife.

Original entry on oeis.org

0, 0, 0, 0, 24, 240, 22320, 1330560, 112210560, 11183235840, 1340192044800, 189443216793600, 31267307962598400, 5964702729085900800, 1303453560329957836800, 323680816052170536960000, 90679832709074132299776000, 28473630606612014817337344000

Offset: 1

Feng Jishe, Jan 09 2016

nonn

We assume that the chairs are uniform and indistinguishable.
First we arrange the females in alternating seats by circular permutation, there are (n-1)! ways. Secondly, we evaluate the number F_{n}, ways of arranging males in the remaining seats as mentioned in the definition above.
By the principle of inclusion-exclusion and theory of rook polynomial Vl, we obtain that a_{n} = (n-1)!*F_{n}, F_{n} = sum(-1)^{k}*r_{k}(B3)*(n-k)! where r_{k}(B3) is the number of ways of putting k non-taking rooks on positions 1's of B3, and the rook polynomials are R_{B3}(x) = sum r_{k}(B3)*x^{k}.
Also F_{n} = per(B3), here per(B3) denotes the permanent of matrix (board) B3, but it is very difficult problem to evaluate the value, per(B3).

			For d=1, the sequence a_{n} is the classical menage sequence A094047.
For d=2 (the current sequence), the F(n)s are 0, 0, 0, 0, 1, 2, 31, 264, 2783, 30818, 369321, ... which is A004307(n) then the sequence a_{n} is 0, 0, 0, 0, 24, 240, 22320, 1330560, 112210560, 11183235840, 1340192044800,...
For d=3, the F(n)s are 0, 0, 0, 0, 0, 0, 1, 2, 78, 888, 13909, ... which is A184965, and a(n) = (n-1)!*A184965(n).

G. Polya, Aufgabe 424, Arch. Math. Phys. (3) 20 (1913) 271.
John Riordan. The enumeration of permutations with three-ply staircase restrictions.

Alois P. Heinz, Table of n, a(n) for n = 1..253
E. Rodney Canfield and Nicholas C. Wormald, Menage numbers, bijections and P-recursiveness, Discrete Mathematics, 63 (2--3)(1987): 117--129.
Bruno Codenotti, Giovanni Resta, On the permanent of certain circulant matrices, in Algebraic Combinatorics and Computer Science. 513-532. 2001.
Feng Jishe, Illustration
Yiting Li, Ménage Numbers and Ménage Permutations, Journal of Integer Sequences, Vol. 18 (2015), #15.6.8.
M. Marcus and H. Mint, On the relation between the determinant and the permanent, Illinois J. Math. 5 (1961): 376-381.
N. Metropolis, M. L. Stein, P. R. Stein, Permanents of cyclic (0,1) matrices, J. Combin. Theory, 7 (1969), 291-321.
Giovanni Sburlati, On the values of permanents of (0,1) circulant matrices with three ones per row, Linear Algebra and its Applications. 408 (2005) 284--297.
Vladimir Shevelev, Peter J.C. Moses, The menage problem with a fixed couple, arXiv:1101.5321 [math.CO], 2011-2015.
L. G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979): 189-201.
Vijay V. Vazirani, Milhalis Yannakakis, Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs, Discrete Applied Mathematics, 25(1989): 179-190.
M. Wyman and L. Moser, On the problème des ménages, Canad. J. Math., 10 (1958), 468-480.

Cf. A004307, A094047, A184965.

b[n_, n0_] := Permanent[Table[If[(0 <= j - i && j - i < n - n0) || j - i < -n0, 1, 0], {i, 1, n}, {j, 1, n}]];
A004307[n_] := b[n, 4];
a[n_] := (n - 1)!*A004307[n];
Array[a, 18] (* Jean-François Alcover, Oct 08 2017 *)

a(n) = (n-1)! * A004307(n). - Andrew Howroyd, Sep 19 2017

a(12)-a(18) from Andrew Howroyd, Sep 19 2017

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

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

A184965 Number of permutations p of [n] such that (n-p(i)+i) mod n >= 6 for all i.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A189389 Number of permutations p of [n] such that (n-p(i)+i) mod n >= 5 for all i.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

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

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

Views

Author

Keywords

Links

Crossrefs

Formula

A267060 a(n) = number of different ways to seat a set of n married male-female couples at a round table so that men and women alternate and every man is separated by at least d = 2 men from his wife.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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