A002524 -id:A002524 - cp's OEIS frontend

A072853 Number of permutations satisfying i-2<=p(i)<=i+6, i=1..n.

1, 2, 6, 18, 54, 162, 486, 1394, 3991, 11593, 33772, 98320, 286072, 831952, 2418664, 7030816, 20441944, 59441521, 172843609, 502580846, 1461344622, 4249102850, 12354982862, 35924300898, 104456501102, 303726483778, 883140022543

Offset: 1

Vladimir Baltic, Jul 25 2002

nonn

R. H. Hardin, Table of n, a(n) for n=1..400
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (April, 2010), 119-135
Index entries for linear recurrences with constant coefficients, signature (1, 2, 4, 8, 14, 26, 44, 56, -11, -19, -28, -28, 0, -8, -20, -20, 0, 5, 11, 10, 0, 0, 2, 2, 0, 0, -1, -1).

Cf. A002524..A002529, A072827, A072850..A072856, A079955..A080014.

Recurrence: a(n)= a(n - 1) + 2*a(n - 2) + 4*a(n - 3) + 8*a(n - 4) + 14*a(n - 5) + 26*a(n - 6) + 44*a(n - 7) + 56*a(n - 8) - 11*a(n - 9) - 19*a(n - 10) - 28*a(n - 11) - 28*a(n - 12) - 8*a(n - 14) - 20*a(n - 15) - 20*a(n - 16) + 5*a(n - 18) + 11*a(n - 19) + 10*a(n - 20) + 2*a(n - 23) + 2*a(n - 24) - a(n - 27) - a(n - 28).

G.f.: - (x^20 + x^18 - 2*x^16 - 2*x^14 - 6*x^12 - 2*x^11 - 4*x^10 - 4*x^9 + 12*x^8 + 2*x^7 + 8*x^6 + 6*x^5 + 4*x^4 + 2*x^3 + x^2 - 1)/(x^28 + x^27 - 2*x^24 - 2*x^23 - 10*x^20 - 11*x^19 - 5*x^18 + 20*x^16 + 20*x^15 + 8*x^14 + 28*x^12 + 28*x^11 + 19*x^10 + 11*x^9 - 56*x^8 - 44*x^7 - 26*x^6 - 14*x^5 - 8*x^4 - 4*x^3 - 2*x^2 - x + 1).

A072854 Number of permutations satisfying i-3<=p(i)<=i+4, i=1..n.

Original entry on oeis.org

1, 2, 6, 24, 96, 330, 1066, 3451, 11581, 39264, 132784, 446460, 1497108, 5023696, 16878488, 56739141, 190697893, 640763258, 2152824662, 7233281108, 24304468132, 81666680202, 274410023170, 922040339607, 3098121457769

Offset: 1

Vladimir Baltic, Jul 25 2002

nonn

R. H. Hardin, Table of n, a(n) for n=1..400
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (April, 2010), 119-135
Index entries for linear recurrences with constant coefficients, signature (0, 3, 10, 24, 58, 128, 226, 164, 66, 8, 50, -72, -374, -640, -630, -518, -390, -426, -466, -216, 94, 48, 22, 52, 38, 48, 22, -8, -2, 0, -2, -1, -2, -1).

Cf. A002524..A002529, A072827, A072850..A072856, A079955..A080014.

Recurrence: a(n) = 3*a(n - 2) + 10*a(n - 3) + 24*a(n - 4) + 58*a(n - 5) + 128*a(n - 6) + 226*a(n - 7) + 164*a(n - 8) + 66*a(n - 9) + 8*a(n - 10) + 50*a(n - 11) - 72*a(n - 12) - 374*a(n - 13) - 640*a(n - 14) - 630*a(n - 15) - 518*a(n - 16) - 390*a(n - 17) - 426*a(n - 18) - 466*a(n - 19) - 216*a(n - 20) + 94*a(n - 21) + 48*a(n - 22) + 22*a(n - 23) + 52*a(n - 24) + 38*a(n - 25) + 48*a(n - 26) + 22*a(n - 27) - 8*a(n - 28) - 2*a(n - 29) - 2*a(n - 31) - a(n - 32) - 2*a(n - 33) - a(n - 34).

G.f.: - (x^27 + x^26 + x^25 - x^24 + 4*x^22 + 4*x^21 - 16*x^20 - 23*x^19 - 29*x^18 + x^17 - 3*x^16 - 20*x^15 - 8*x^14 + 44*x^13 + 56*x^12 + 79*x^11 + 67*x^10 + 63*x^9 + 69*x^8 + 76*x^7 + 36*x^6 + 24*x^5 + 16*x^4 + 7*x^3 + x^2 - x - 1)/(x^34 + 2*x^33 + x^32 + 2*x^31 + 2*x^29 + 8*x^28 - 22*x^27 - 48*x^26 - 38*x^25 - 52*x^24 - 22*x^23 - 48*x^22 - 94*x^21 + 216*x^20 + 466*x^19 + 426*x^18 + 390*x^17 + 518*x^16 + 630*x^15 + 640*x^14 + 374*x^13 + 72*x^12 - 50*x^11 - 8*x^10 - 66*x^9 - 164*x^8 - 226*x^7 - 128*x^6 - 58*x^5 - 24*x^4 - 10*x^3 - 3*x^2 + 1).

A072855 Number of permutations satisfying i-3<=p(i)<=i+5, i=1..n.

Original entry on oeis.org

1, 2, 6, 24, 96, 384, 1374, 4718, 16275, 57749, 206756, 739780, 2637348, 9378840, 33318804, 118439044, 421340612, 1499388117, 5335199213, 18980987054, 67522942850, 240204885524, 854523535096, 3040023558788, 10815153542594

Offset: 1

Vladimir Baltic, Jul 25 2002

nonn

R. H. Hardin, Table of n, a(n) for n = 1..400
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (April, 2010), 119-135
Index entries for linear recurrences with constant coefficients, signature (1, 3, 8, 20, 46, 114, 242, 354, -250, -490, -660, -496, -24, -1242, -2430, -2270, -566, 2241, 5071, 4259, -632, 1392, 6396, 5596, -132, 1316, -6220, -11116, 736, 344, -5128, -3684, 1148, -388, 980, 1665, 239, -199, 688, 540, -106, 50, -78, -102, -58, 22, -44, -40, 0, -2, 2, 2, 2, -1, 1, 1).

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014.

G.f.: -(1- 2*x^2 - 7*x^3 - 16*x^4 - 28*x^5 - 32*x^6 - 58*x^7 - 156*x^8 + 67*x^9 + 76*x^10 + 68*x^11 + 145*x^12 + 12*x^13 + 156*x^14 + 180*x^15 + 704*x^16 + 344*x^17 - 454*x^18 - 276*x^19 - 480*x^20 + 158*x^21 - 260*x^22 - 116*x^23 - 780*x^24 - 756*x^25 + 168*x^26 + 206*x^27 + 900*x^28 - 340*x^29 + 126*x^30 + 132*x^31 + 276*x^32 + 28*x^33 + 16*x^34 + 24*x^35 - 107*x^36 + 36*x^37 - 14*x^38 - 7*x^39 - 28*x^40 - 4*x^42 - 2*x^43 + 4*x^44 - x^45 + x^48) / (-1 + x + 3*x^2 + 8*x^3 + 20*x^4 + 46*x^5 + 114*x^6 + 242*x^7 + 354*x^8 - 250*x^9 - 490*x^10 - 660*x^11 - 496*x^12 - 24*x^13 - 1242*x^14 - 2430*x^15 - 2270*x^16 - 566*x^17 + 2241*x^18 + 5071*x^19 + 4259*x^20 - 632*x^21 + 1392*x^22 + 6396*x^23 + 5596*x^24 - 132*x^25 + 1316*x^26 - 6220*x^27 - 11116*x^28 + 736*x^29 + 344*x^30 - 5128*x^31 - 3684*x^32 + 1148*x^33 - 388*x^34 + 980*x^35 + 1665*x^36 + 239*x^37 - 199*x^38 + 688*x^39 + 540*x^40 - 106*x^41 + 50*x^42 - 78*x^43 - 102*x^44 - 58*x^45 + 22*x^46 - 44*x^47 - 40*x^48 - 2*x^50 + 2*x^51 + 2*x^52 + 2*x^53 - x^54 + x^55 + x^56). - Vaclav Kotesovec, Dec 01 2012

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

A002525 Number of permutations according to distance.

Original entry on oeis.org

0, 1, 2, 4, 10, 24, 55, 128, 300, 700, 1632, 3809, 8890, 20744, 48406, 112960, 263599, 615120, 1435416, 3349624, 7816528, 18240289, 42564706, 99327052, 231785058, 540883000, 1262179815, 2945365040, 6873169028, 16038912628

Offset: 0

N. J. A. Sloane

nonn

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
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.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Index entries for linear recurrences with constant coefficients, signature (2,0,2,0,-1).

Cf. A002524.

I:=[0,1,2,4,10]; [n le 5 select I[n] else 2*Self(n-1) +2*Self(n-3) -Self(n-5): n in [1..41]]; // G. C. Greubel, Jan 22 2022

A002525:=z/(1-2*z-2*z**3+z**5); # conjectured by Simon Plouffe in his 1992 dissertation

a[n_ /; n <= 2] := n; a[3]=4; a[4]=10; a[n_] := a[n] = 2*a[n-1] + 2*a[n-3] - a[n-5]; Table[a[n], {n, 0, 29}] (* Jean-François Alcover, Mar 12 2014 *)

a(n) = {z = x + x*O(x^n); gf = z/(1-2*z-2*z^3+z^5); polcoeff(gf, n);} \\ Michel Marcus, Mar 11 2014

[( x/(1-2*x-2*x^3+x^5) ).series(x,n+1).list()[n] for n in (0..40)] # G. C. Greubel, Jan 22 2022

G.f.: x/(1 - 2*x - 2*x^3 + x^5). - Simon Plouffe

a(n) = Sum_{k=0..n-1} A002524(k). - Sean A. Irvine, Mar 10 2014

More terms from Sean A. Irvine, Mar 10 2014

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

Original entry on oeis.org

1, 0, 0, 1, 1, 1, 1, 3, 3, 4, 6, 9, 12, 16, 24, 33, 46, 64, 91, 127, 177, 249, 349, 489, 684, 960, 1345, 1884, 2640, 3700, 5185, 7264, 10180, 14265, 19989, 28009, 39249, 54999, 77067, 107992, 151326, 212049, 297136, 416368, 583444, 817561, 1145622, 1605324, 2249491, 3152139, 4416993

Offset: 0

Vladimir Baltic, Jan 24 2003

nonn

Also the number of permutations satisfying -k<=p(i)-i<=r and p(i)-i not in I, i=1..n, with k=2, r=2, I={0,-1}.

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.

Michael De Vlieger, Table of n, a(n) for n = 0..6829
Michael A. Allen and Kenneth Edwards, Connections between two classes of generalized Fibonacci numbers squared and permanents of (0,1) Toeplitz matrices, arXiv:2107.02589 [math.CO], 2021.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (2010), 119-135
Tomislav Došlić, Mate Puljiz, Stjepan Šebek, and Josip Žubrinić, On a variant of Flory model, arXiv:2210.12411 [math.CO], 2022.
P. L. Krapivsky and J. M. Luck, Jamming and metastability in one dimension: from the kinetically constrained Ising chain to the Riviera model, arXiv:2211.12815 [cond-mat.stat-mech], 2022.
Index entries for linear recurrences with constant coefficients, signature (0,1,1,1,0,-1).

Cf. A002524..A002529, A072827, A072850..A072856, A079955..A080014.

LinearRecurrence[{0,1,1,1,0,-1},{1,0,0,1,1,1},60] (* Harvey P. Dale, Aug 08 2019 *)

Recurrence: a(n) = a(n-2)+a(n-3)+a(n-4)-a(n-6).

G.f.: -(x^2-1)/(x^6-x^4-x^3-x^2+1)

A224811 Number of subsets of {1,2,...,n-8} without differences equal to 2, 4, 6 or 8.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 6, 9, 12, 16, 20, 25, 30, 36, 48, 64, 88, 121, 165, 225, 300, 400, 520, 676, 884, 1156, 1530, 2025, 2700, 3600, 4800, 6400, 8480, 11236, 14840, 19600, 25900, 34225, 45325, 60025, 79625, 105625, 140075, 185761, 246101, 326041, 431676, 571536, 756756, 1002001, 1327326, 1758276, 2329782, 3087049, 4090296, 5419584

Offset: 0

Vladimir Baltic, May 18 2013

nonn

Number of permutations (p(1), p(2), ..., p(n)) satisfying -k <= p(i)-i <= r and p(i)-i in the set I, i=1..n, with k=2, r=8, I={-2,0,8}.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Michael A. Allen, On a Two-Parameter Family of Generalizations of Pascal's Triangle, arXiv:2209.01377 [math.CO], 2022.
Vladimir Baltic, On the number of certain types of strongly restricted permutations, Applicable Analysis and Discrete Mathematics Vol. 4, No 1 (April, 2010), 119-135
Index entries for linear recurrences with constant coefficients, signature (1, 0, 0, 0, 1, -1, 1, -1, 1, 2, -1, 1, 0, 0, -2, 1, -2, 0, 0, -1, 0, 0, 0, 0, 1).

Cf. A002524-A002529, A072827, A072850-A072856, A079955-A080014, A217694,A224808-A224810.

CoefficientList[Series[(1 - x^10 - x^5 - x^7 + x^15)/((1 - x)*(1 + x)*(x^2 - x + 1)*(x^3 + x^2 - 1)*(x^6 - x^2 - 1)*(x^12 + x^10 + x^8 + 2*x^6 + x^4 + 1)), {x, 0, 50}], x] (* G. C. Greubel, Oct 28 2017 *)

x='x+O('x^50); Vec((1-x^10-x^5-x^7+x^15)/((1-x)*(1+x)*(x^2-x+1)*( x^3+x^2-1)*(x^6-x^2-1)*(x^12+x^10+x^8+2*x^6+x^4+1) )) \\ G. C. Greubel, Oct 28 2017

a(n) = a(n-1) +a(n-5) -a(n-6) +a(n-7) -a(n-8) +a(n-9) +2*a(n-10) -a(n-11) +a(n-12) -2*a(n-15) +a(n-16) -2*a(n-17) -a(n-20) +a(n-25).
G.f.: (1-x^10-x^5-x^7+x^15) / ( (1-x) *(1+x) *(x^2-x+1) *(x^3+x^2-1) *(x^6-x^2-1) *(x^12+x^10+x^8+2*x^6+x^4+1) ).
a(2*k) = (A003520(k))^2,
a(2*k+1) = A003520(k) * A003520(k+1)

cp's OEIS Frontend

A072853 Number of permutations satisfying i-2<=p(i)<=i+6, i=1..n.

Views

Author

Keywords

Links

Crossrefs

Formula

A072854 Number of permutations satisfying i-3<=p(i)<=i+4, i=1..n.

Views

Author

Keywords

Links

Crossrefs

Formula

A072855 Number of permutations satisfying i-3<=p(i)<=i+5, i=1..n.

Views

Author

Keywords

Links

Crossrefs

Formula

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

Keywords

Comments

Links

Crossrefs

Extensions

A154658 Number of permutations of length n within distance 9.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A002525 Number of permutations according to distance.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica