A000183 -id:A000183 - 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 *)

A061702 Triangle T(n,k) defined by Sum_{n >= 0,m >= 0} T(n,m)x^my^n = 1 + y(1 + 3x - 4x^2y - 3x^2y^2 - 3x^3y^2 + 4x^4y^3)/((1 - y - 2xy - xy^2 + x^3y^3)(1 - xy)).

Original entry on oeis.org

1, 1, 3, 1, 6, 5, 1, 9, 18, 6, 1, 12, 42, 44, 9, 1, 15, 75, 145, 95, 13, 1, 18, 117, 336, 420, 192, 20, 1, 21, 168, 644, 1225, 1085, 371, 31, 1, 24, 228, 1096, 2834, 3880, 2588, 696, 49, 1, 27, 297, 1719, 5652, 10656, 11097, 5823, 1278, 78, 1, 30, 375, 2540, 10165

Offset: 0

Vladeta Jovovic, Jun 18 2001

It is uncertain if the initial term should be 0 or 1. Both make sense. I have changed the data line to start with 1, in agreement with Riordan (1954). - N. J. A. Sloane, Jun 28 2015

See Riordan 1954 page 21 equation (24). - Michael Somos, Aug 26 2015

			Triangle begins:
1,
1,3,
1,6,5,
1,9,18,6,
1,12,42,44,9,
1,15,75,145,95,13,
1,18,117,336,420,192,20,
1,21,168,644,1225,1085,371,31,
1,24,228,1096,2834,3880,2588,696,49,
1,27,297,1719,5652,10656,11097,5823,1278,78,
1,30,375,2540,10165,24626,35045,29380,12535,2310,125,
... (from _N. J. A. Sloane_, Jun 28 2015)
Sum_{n, k} T(n, k) u^n t^k = 1 + (1 + 3*t)*u + (1 + 6*t + 5*t^2)*u^2 + ...

R. P. Stanley, Enumerative Combinatorics I, Example 4.7.17.

J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23. [Annotated scanned copy] See Table 1.

Cf. A000183, row sums: A061703, third column: A000338, fourth column: A000561, fifth column: A000562, sixth column: A000563, seventh column: A000564, eighth column: A000565.

max = 11; f[x_, y_] := 1 + y*(1 + 3*x - 4*x^2*y - 3*x^2*y^2 - 3*x^3*y^2 + 4*x^4*y^3)/((1 - y - 2*x*y - x*y^2 + x^3*y^3)*(1 - x*y)); se = Series[f[x, y], {x, 0, max}, {y, 0, max}]; coes = CoefficientList[se, {x, y}] ; t[n_, k_] := coes[[k, n]]; Flatten[ Table[t[n, k], {n, 1, max}, {k, 1, n}]](* Jean-François Alcover, Oct 24 2011 *)

Edited by N. J. A. Sloane, Jun 28 2015

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.

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

Original entry on oeis.org

0, 1, 1, 11, 60, 435, 3473, 31315, 313227, 3445641, 41341502, 537313583, 7520316423, 112771887719, 1803821926465, 30656189582521, 551659191788556, 10478765887885181, 209522984620760153, 4398943767896801309, 96755196700729056267, 2224901906327124750355

Offset: 0

Alois P. Heinz, Mar 09 2019

nonn

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

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

Cf. A000179, A000183.

a(n) = A000179(n+2) - A000183(n+2).

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

A061703 G.f.: 2x(2-2x-3x^2+2x^3)/((1-3x-x^2+x^3)*(1-x)).

Original entry on oeis.org

0, 4, 12, 34, 108, 344, 1104, 3546, 11396, 36628, 117732, 378426, 1216380, 3909832, 12567448, 40395794, 129844996, 417363332, 1341539196, 4312135922, 13860583628, 44552347608, 143205490528, 460308235562, 1479577849604

Offset: 0

Vladeta Jovovic, Jun 18 2001

R. P. Stanley, Enumerative Combinatorics I, Example 4.7.17.

Index entries for linear recurrences with constant coefficients, signature (4,-2,-2,1)

Row sums of A061702, A000183.

A264801 Number of essentially different seating arrangements for 2n couples around a circular table with 4n seats such that no spouses are neighbors, the neighbors of each person have opposite gender and no person's neighbors belong to the same couple.

Original entry on oeis.org

0, 6, 2400, 6375600, 45927907200, 713518388352000, 21216194909362252800, 1105729617210350356224000, 94398452626533646953922560000, 12514511465855205467497303154688000, 2467490887755897725667792936979169280000, 698323914872709997998407130752506728284160000

Offset: 1

Hugo Pfoertner, Nov 25 2015

nonn

This might be called the "maximum diversity" menage problem. Arrangements that differ only by rotation or reflection are excluded by the following conditions: Seat number 1 is assigned to person A. Seat number 2 can only be taken by a person of the same gender as A. The second condition forces an mmffmmff... pattern.

			a(1)=0 because with 2 couples it is impossible to satisfy all three conditions.
a(2)=6 because only the following arrangements are possible with 4 couples: ABdaCDbc, ABcaDCbd, ACdaBDcb, ACbaDBcd, ADcaBCdb, ADbaCBdc. This corresponds to the (2*2-1)! possibilities for persons B, C and D to choose a seat. After the positions of A, B, C and D are fixed, only A000183(2*2)=1 possibility remains to arrange their spouses a, b, c  and d.

Cf. A000183, A007060, A094047, A114939, A258338.

a000183(N)={my(a0=[0,0,0,1,2,20],a=vector(N),
f(x)=fibonacci(x-1)+fibonacci(x+1)+2;);
if(N<7,a=a0[1..N],for(k=1,6,a[k]=a0[k]);
for(n=7,N,a[n] = (-1)^n*(4*n+f(n)) +
 (n/(n-1))*((n+1)*a[n-1] + 2*(-1)^n*f(n-1))
  - ((2*n)/(n-2))*((n-3)*a[n-2] + (-1)^n*f(n-2))
  + (n/(n-3))*((n-5)*a[n-3] + 2*(-1)^(n-1)*f(n-3))
  + (n/(n-4))*(a[n-4] + (-1)^(n-1)*f(n-4))));a};
a264901(limit)={my(a183=a000183(2*limit)); for(n=1,limit,print1((2*n-1)!*a183[2*n],", "))};
a264901(12) \\ Hugo Pfoertner, Sep 05 2020

a(n) = (2*n-1)! * A000183(2*n).

A002633 Related to discordant permutations.

Original entry on oeis.org

1, -3, 5, -3, 9, -3, -51, -675, -5871, -46467, -331371, -1852227, -920295, 224455293, 5571057501, 104877816093, 1781775072801, 28519837563645, 431525731169061, 5994769814117757, 68879336771960361, 346333945918252797, -15047168730918615315, -793523760950138583843

Offset: 0

N. J. A. Sloane

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

K. Yamamoto, Structure polynomial of Latin rectangles and its application to a combinatorial problem, Memoirs of the Faculty of Science, Kyusyu University, Series A, 10 (1956), 1-13.
K. Yamamoto, Structure polynomial of Latin rectangles and its application to a combinatorial problem, Memoirs of the Faculty of Science, Kyusyu University, Series A, 10 (1956), 1-13. [Annotated scanned copy]

Cf. A213170, A269953.

a[ n_ ] := a[ n ]=(2n-5)a[ n-1 ]-(n-1)(n-4)a[ n-2 ]-(n-1)(n-2)a[ n-3 ]; a[ 0 ]=1; a[ 1 ]=-3; a[ 2 ]=5; Table[ a[ n ], {n, 0, 24} ] (* Typo fixed by Vaclav Kotesovec, Mar 20 2014 *)

a(n) - (2n-5)*a(n-1) + (n-1)*(n-4)*a(n-2) + (n-1)*(n-2)*a(n-3) = 0.
From Mélika Tebni, Mar 02 2022: (Start)
a(n) = Sum_{k=0..n} A213170(k)*A269953(n, k).
E.g.f.: exp(-x*(3 - x) / (1 - x)). (End)

More terms from Wouter Meeussen

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

A061702 Triangle T(n,k) defined by Sum_{n >= 0,m >= 0} T(n,m)*x^m*y^n = 1 + y*(1 + 3*x - 4*x^2*y - 3*x^2*y^2 - 3*x^3*y^2 + 4*x^4*y^3)/((1 - y - 2*x*y - x*y^2 + x^3*y^3)*(1 - x*y)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

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

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

Views

Author

Keywords

Links

Crossrefs

Formula

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

A061703 G.f.: 2*x*(2-2*x-3*x^2+2*x^3)/((1-3*x-x^2+x^3)*(1-x)).

Views

Author

Keywords

References

Links

Crossrefs

A264801 Number of essentially different seating arrangements for 2n couples around a circular table with 4n seats such that no spouses are neighbors, the neighbors of each person have opposite gender and no person's neighbors belong to the same couple.

Views

Author

Keywords

A061702 Triangle T(n,k) defined by Sum_{n >= 0,m >= 0} T(n,m)x^my^n = 1 + y(1 + 3x - 4x^2y - 3x^2y^2 - 3x^3y^2 + 4x^4y^3)/((1 - y - 2xy - xy^2 + x^3y^3)(1 - xy)).

A061703 G.f.: 2x(2-2x-3x^2+2x^3)/((1-3x-x^2+x^3)*(1-x)).