A002526 -id:A002526 - cp's OEIS frontend

A002527 Number of permutations p on the set [n] with the properties that abs(p(i)-i) <= 3 for all i and p(1) <= 3.

0, 1, 2, 6, 18, 60, 184, 560, 1695, 5200, 15956, 48916, 149664, 458048, 1402360, 4294417, 13149210, 40259178, 123260854, 377395940, 1155508592, 3537919648, 10832298239, 33165996032, 101546731816, 310913195800, 951945967120, 2914642812096, 8923975209168

Offset: 0

N. J. A. Sloane

nonn

a(n) is also the permanent of the n X n matrix that has ones on its diagonal, ones on its three superdiagonals, ones on its three subdiagonals (with the exception of a single zero in the (4,1)-entry), and is zero elsewhere.

This is the second row of Kløve's Table 3.

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

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 92 terms from Nathaniel Johnston)
Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement. Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.
R. Lagrange, Quelques résultats dans la métrique des permutations, Annales Scientifiques de l'École Normale Supérieure, Paris, 79 (1962), 199-241.
Index entries for linear recurrences with constant coefficients, signature (2,2,0,10,8,-2,-16,-10,-2,4,2,0,2,1).

with(LinearAlgebra):
A002527:= n-> `if`(n=0, 0, Permanent(Matrix(n, (i, j)->
              `if`(abs(j-i)<4 and [i, j]<>[4, 1], 1, 0)))):
seq(A002527(n), n=0..20);

A002527[n_] := If [n == 0, 0, Permanent[Table[If [Abs[j-i]<4 && {i, j} != {4, 1}, 1, 0], {i, 1, n}, {j, 1, n}]]]; Table [A002527[n], {n, 0, 25}] (* Jean-François Alcover, Mar 11 2014, after Maple *)

From Nathaniel Johnston, Apr 03 2011: (Start)
a(n) = A002526(n) - A188379(n-1).
a(n) = a(n-1) + A002526(n-1) + A002529(n-1). (End)
G.f.: x*(x^7+2*x^6-2*x^4-2*x^3-1) / (x^14 +2*x^13 +2*x^11 +4*x^10 -2*x^9 -10*x^8 -16*x^7 -2*x^6 +8*x^5 +10*x^4 +2*x^2 +2*x-1). - Alois P. Heinz, Apr 07 2011

Name and comments edited, and terms after a(11) added by Nathaniel Johnston, Apr 03 2011

A079962 Number of permutations satisfying -k <= p(i) - i <= r and p(i) - i not in I, i=1..n, with k=1, r=5, I={1,3}.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 9, 14, 22, 36, 58, 94, 153, 247, 399, 646, 1045, 1691, 2737, 4428, 7164, 11592, 18756, 30348, 49105, 79453, 128557, 208010, 336567, 544577, 881145, 1425722, 2306866, 3732588, 6039454, 9772042, 15811497, 25583539, 41395035

Offset: 0

Vladimir Baltic, Feb 19 2003

Number of compositions (ordered partitions) of n into elements of the set {1,3,5,6}. - Mark Dols, Aug 20 2010

D. H. Lehmer, Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), pp. 755-770. North-Holland, Amsterdam, 1970.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135
Index entries for linear recurrences with constant coefficients, signature (1,0,1,0,1,1).

Cf. A002524, A002525, A002526, A002527, A002528, A002529, A072827, A072850, A072851, A072852, A072853, A072854, A072855, A072856, A079955 - A080014.

[Round(Fibonacci(n+3)/4): n in [0..40]]; // G. C. Greubel, Jan 21 2022

with(combinat,fibonacci): seq(round(fibonacci(n+3)/4),n=0..38) # Mircea Merca, Jan 04 2011

LinearRecurrence[{1,0,1,0,1,1}, {1,1,1,2,3,5}, 41] (* G. C. Greubel, Jan 21 2022 *)

a(n)=fibonacci(n+3)\/4 \\ Charles R Greathouse IV, Oct 07 2015

[(1/4)*(fibonacci(n+3) + chebyshev_U(n,1/2) + chebyshev_U(2*n,1/2)) for n in (0..40)] # G. C. Greubel, Jan 21 2022

a(n) = a(n-1) + a(n-3) + a(n-5) + a(n-6).
G.f.: 1/((1+x+x^2)*(1-x+x^2)*(1-x-x^2)).
a(n+1)/a(n) -> golden ratio A001622. - Roger L. Bagula, Mar 13 2006
a(n) + a(n+2) + a(n+4) = Fibonacci(n+5). - Mark Dols, Aug 20 2010
a(n) = round(Fibonacci(n+3)/4). - Mircea Merca, Jan 04 2011
a(n+6) - a(n) = A000045(n+6). - Paul Curtz, Jun 29 2013
a(n) + a(n+1) + a(n+2) = A024490(n+6). - R. J. Mathar, Jun 30 2013
a(n) - a(n-1) + a(n-2) = A094686(n). - R. J. Mathar, Jun 30 2013
4*a(n) = A057078(n) + A010892(n) + A000045(n+3). - R. J. Mathar, Nov 02 2016

A154654 Number of permutations of length n within distance 5.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 3720, 17304, 76110, 329462, 1441923, 6487445, 29555588, 135025756, 615260976, 2791161792, 12618600768, 57008446080, 257708989200, 1166042944564, 5279435858788, 23908888017477, 108262665958797, 490132089640318, 2218641353956314

Offset: 0

Torleiv Kløve, Jan 13 2009

a(n) equals the permanent of the n X n matrix with 1's along the eleven central diagonals and 0's everywhere else. - John M. Campbell, Jul 10 2011

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n=1..400 from R. H. Hardin)
Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.

Cf. A000045, A002524, A002526, A072856.

Column k=5 of A306209.

G.f. is a rational function f(x)/g(x) where f has degree 132 and g has degree 142.

a(0)=1 prepended by Alois P. Heinz, Jan 28 2019

A188491 Number of permutations p on the set [n] with the properties that abs(p(i)-i) <= 3 for all i, p(1) <= 3, and p(4) >= 2.

Original entry on oeis.org

0, 1, 2, 6, 14, 48, 152, 476, 1425, 4340, 13288, 40852, 125124, 382888, 1171612, 3587505, 10985790, 33638142, 102988410, 315318756, 965432832, 2955964296, 9050522241, 27710613432, 84843476928, 259771465608, 795361704776, 2435217884992

Offset: 0

N. J. A. Sloane, Apr 01 2011

nonn

a(n) is also the permanent of the n X n matrix that has ones on its diagonal, ones on its three superdiagonals (with the exception of a single zero in the (1,4)-entry), ones on its three subdiagonals (with the exception of a single zero in the (4,1)-entry), and is zero elsewhere.

This is row 5 of Kløve's Table 3.

Nathaniel Johnston, Table of n, a(n) for n = 0..100
Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement. Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.

a:= n-> (Matrix(13, (i, j)-> `if`(i=j-1, 1, `if`(i=13, [-1, -3, -3, -5, -9, -7, 3, 19, 21, 13, 3, 3, 1][j], 0)))^n. <<0, 0, 1, (0$6), 1, 2, 6, 14>>)[9, 1]: seq(a(n), n=0..30);  # Alois P. Heinz, Apr 08 2011

a[n_] := ((Table[Which[i == j-1, 1, i == 13, {-1, -3, -3, -5, -9, -7, 3, 19, 21, 13, 3, 3, 1}[[j]], True, 0], {i, 1, 13}, {j, 1, 13}] // MatrixPower[#, n]&).{0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 2, 6, 14})[[9]]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 17 2014, after Alois P. Heinz *)

a(n) = A002526(n-1) + A002528(n-1) + A188494(n-1). - Nathaniel Johnston, Apr 08 2011

G.f.: -x*(x^3+x^2-1)*(x^3+2*x^2+x+1) / (x^13 +3*x^12 +3*x^11 +5*x^10 +9*x^9 +7*x^8 -3*x^7 -19*x^6 -21*x^5 -13*x^4 -3*x^3 -3*x^2 -x+1).

Name and comments edited by Nathaniel Johnston, Apr 08 2011

A188494 Number of permutations p on the set [n] with the properties that abs(p(i)-i) <= 3 for all i and p(1) <= 2.

Original entry on oeis.org

0, 1, 2, 4, 12, 42, 138, 414, 1235, 3764, 11604, 35664, 109132, 333652, 1021220, 3127709, 9578526, 29326904, 89785684, 274896606, 841682902, 2577075290, 7890425175, 24158602552, 73968049928, 226473538032, 693411153800, 2123068036904, 6500352097064

Offset: 0

N. J. A. Sloane, Apr 01 2011

a(n) is also the permanent of the n X n matrix that has ones on its diagonal, ones on its three superdiagonals, ones on its three subdiagonals (with the exception of zeros in the (3,1) and (4,1)-entries), and is zero elsewhere.

This is row 8 of Kløve's Table 3.

Harvey P. Dale, Table of n, a(n) for n = 0..1000(first 93 terms from Nathaniel Johnston)
Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.
Index entries for linear recurrences with constant coefficients, signature (1,3,3,13,21,19,3,-7,-9,-5,-3,-3,-1).

with(LinearAlgebra):
A188494:= n-> `if`(n=0, 0, Permanent(Matrix(n, (i, j)->
              `if`(abs(j-i)<4 and [i, j]<>[3, 1] and [i, j]<>[4, 1], 1, 0)))):
seq(A188494(n), n=0..20);

LinearRecurrence[{1,3,3,13,21,19,3,-7,-9,-5,-3,-3,-1},{0,1,2,4,12,42,138,414,1235,3764,11604,35664,109132},30] (* Harvey P. Dale, Dec 27 2015 *)

concat(0, Vec(x*(x^6 +x^5 -x^4 -x^3 -x^2 +x +1) / (x^13 +3*x^12 +3*x^11 +5*x^10 +9*x^9 +7*x^8 -3*x^7 -19*x^6 -21*x^5 -13*x^4 -3*x^3 -3*x^2 -x +1) + O(x^100))) \\ Colin Barker, Dec 13 2014

From Nathaniel Johnston, Apr 10 2011: (Start)
a(n) = A188491(n+1) - A002528(n) - A002526(n).
a(n) = A002526(n-1) + A002527(n-1).
(End)
G.f.: x*(x^6 +x^5 -x^4 -x^3 -x^2 +x +1) / (x^13 +3*x^12 +3*x^11 +5*x^10 +9*x^9 +7*x^8 -3*x^7 -19*x^6 -21*x^5 -13*x^4 -3*x^3 -3*x^2 -x +1). - Colin Barker, Dec 13 2014

Name and comments edited, and a(12)-a(28) from Nathaniel Johnston, Apr 10 2011

A154655 Number of permutations of length n within distance 6.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 5040, 30960, 172200, 899064, 4553166, 22934774, 116914351, 610093513, 3222826972, 17101449940, 90706002192, 479654768640, 2527274267136, 13280313508416, 69734129749632, 366283822765632, 1925290900630896, 10126754515065868

Offset: 0

Torleiv Kløve, Jan 13 2009

a(n) equals the permanent of the n X n matrix with 1's along the central thirteen diagonals, and 0's everywhere else. - John M. Campbell, Jul 10 2011

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n=1..400 from R. H. Hardin)
Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.

Cf. A000045, A002524, A002526, A072856, A154654.

Column k=6 of A306209.

G.f. is a rational function f(x)/g(x) where f has degree 482 and g has degree 494.

a(0)=1 prepended by Alois P. Heinz, Jan 28 2019

A154656 Number of permutations of length n within distance 7.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 287280, 1865520, 11345160, 66349464, 381523758, 2193664790, 12764590275, 75796724309, 455383613924, 2750869551868, 16635586999056, 100439873614656, 604666567043712, 3629299734118656, 21736009354060800, 130082373922081536

Offset: 0

Torleiv Kløve, Jan 13 2009

a(n) equals the permanent of the n X n matrix with 1's along the central fifteen diagonals, and 0's everywhere else. - John M. Campbell, Jul 10 2011

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (terms n=1..400 from R. H. Hardin)
Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.

Cf. A000045, A002524, A002526, A072856, A154654.

Column k=7 of A306209.

a(0)=1 prepended by Alois P. Heinz, Jan 28 2019

A154657 Number of permutations of length n within distance 8.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 2943360, 21898800, 152622000, 1017952680, 6623303544, 42700751022, 276054834902, 1805409270031, 12020754177001, 80930279045116, 548117873866228, 3720269813727312, 25239622338694272, 170893063638209664

Offset: 0

Torleiv Kløve, Jan 13 2009

nonn

a(n) equals the permanent of the n X n matrix with 1's along the central seventeen diagonals, and 0's everywhere else. - John M. Campbell, Jul 10 2011

Alois P. Heinz, Table of n, a(n) for n = 0..800 (terms n=1..177 from R. H. Hardin)
Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.

Cf. A000045, A002524, A002526, A072856, A154654-A154656.

Column k=8 of A306209.

a(0)=1 prepended by Alois P. Heinz, Jan 28 2019

A154658 Number of permutations of length n within distance 9.

Original entry on oeis.org

1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800, 33022080, 277280640, 2184341040, 16427628720, 119892387720, 861175365144, 6157828055310, 44222780245622, 321113303226243, 2369364111428885, 17667206334000068, 132553643382927196, 997400200347756816

Offset: 0

Torleiv Kløve, Jan 13 2009

nonn

a(n) equals the permanent of the n X n matrix with 1's along the central nineteen diagonals, and 0's everywhere else. - John M. Campbell, Jul 10 2011

Alois P. Heinz, Table of n, a(n) for n = 0..400 (terms n=1..45 from R. H. Hardin)
Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.

Cf. A000045, A002524, A002526, A072856, A154654-A154657.

Column k=9 of A306209.

a(0)=1 prepended by Alois P. Heinz, Jan 28 2019

A188495 Number of permutations p on the set [n] with the properties that abs(p(i)-i) <= 3 for all i, p(1) <= 2, and p(4) >= 2.

Original entry on oeis.org

0, 1, 2, 4, 10, 36, 120, 368, 1089, 3304, 10168, 31312, 95880, 293120, 896824, 2746569, 8411818, 25756220, 78853410, 241421436, 739183568, 2263249600, 6929580817, 21216729488, 64960656448, 198894856144, 608971496032, 1864533223584, 5708777321872

Offset: 0

N. J. A. Sloane, Apr 01 2011

a(n) is also the permanent of the n X n matrix that has ones on its diagonal, ones on its three superdiagonals (with the exception of a zero in the (1,4)-entry), ones on its three subdiagonals (with the exception of zeros in the (3,1) and (4,1)-entries), and is zero elsewhere.

This is row 10 of Kløve's Table 3.

Nathaniel Johnston, Table of n, a(n) for n = 0..119
Torleiv Kløve, Spheres of Permutations under the Infinity Norm - Permutations with limited displacement. Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.
Index entries for linear recurrences with constant coefficients, signature (2,2,0,10,8,-2,-16,-10,-2,4,2,0,2,1).

with (LinearAlgebra):
A188495:= n-> `if` (n=0, 0, Permanent (Matrix (n, (i, j)->
              `if` (abs(j-i)<4 and [i, j]<>[3, 1] and [i, j]<>[4, 1] and [i, j]<>[1, 4], 1, 0)))):
seq (A188495(n), n=0..20);

a[n_] := Permanent[Table[If[Abs[j - i] < 4 && {i, j} != {3, 1} && {i, j} != {4, 1} && {i, j} != {1, 4}, 1, 0], {i, 1, n}, {j, 1, n}]]; a[1] = 1; Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 20}] (* Jean-François Alcover, Jan 06 2016, adapted from Maple *)

concat(0, Vec(-x*(x +1)*(x^6 +x^5 -x^4 -x^3 -x^2 -x +1) / ((x -1)*(x^13 +3*x^12 +3*x^11 +5*x^10 +9*x^9 +7*x^8 -3*x^7 -19*x^6 -21*x^5 -13*x^4 -3*x^3 -3*x^2 -x +1)) + O(x^100))) \\ Colin Barker, Dec 13 2014

From Nathaniel Johnston, Apr 10 2011: (Start)
a(n) = A188493(n+1) - A188491(n) - A188497(n).
a(n) = A002526(n-1) + A188494(n-1).
(End)
G.f.: -x*(x +1)*(x^6 +x^5 -x^4 -x^3 -x^2 -x +1) / ((x -1)*(x^13 +3*x^12 +3*x^11 +5*x^10 +9*x^9 +7*x^8 -3*x^7 -19*x^6 -21*x^5 -13*x^4 -3*x^3 -3*x^2 -x +1)). - Colin Barker, Dec 13 2014

Name and comments edited, and a(12)-a(28) from Nathaniel Johnston, Apr 10 2011

cp's OEIS Frontend

A002527 Number of permutations p on the set [n] with the properties that abs(p(i)-i) <= 3 for all i and p(1) <= 3.

Views

Author

Keywords

Comments

References

Links

Programs

Maple

Mathematica

Formula

Extensions

A079962 Number of permutations satisfying -k <= p(i) - i <= r and p(i) - i not in I, i=1..n, with k=1, r=5, I={1,3}.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A154654 Number of permutations of length n within distance 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A188491 Number of permutations p on the set [n] with the properties that abs(p(i)-i) <= 3 for all i, p(1) <= 3, and p(4) >= 2.

Views

Author

Keywords

Comments

Links

Programs

Maple

Mathematica

Formula

Extensions

A188494 Number of permutations p on the set [n] with the properties that abs(p(i)-i) <= 3 for all i and p(1) <= 2.

Views

Author

Keywords

Comments

Links

Programs

Maple

Mathematica

PARI

Formula

Extensions

A154655 Number of permutations of length n within distance 6.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A154656 Number of permutations of length n within distance 7.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A154657 Number of permutations of length n within distance 8.

Views

Author