A002524 - OEIS

%I M1600 N0626 #95 Jan 05 2025 19:51:32

%S 1,1,2,6,14,31,73,172,400,932,2177,5081,11854,27662,64554,150639,

%T 351521,820296,1914208,4466904,10423761,24324417,56762346,132458006,

%U 309097942,721296815,1683185225,3927803988,9165743600,21388759708,49911830577,116471963129

%N Number of permutations of length n within distance 2 of a fixed permutation.

%C From _Torleiv Kløve_, Jan 09 2009: (Start)

%C Let V(d,n) be the number of permutations of length n within distance d of a fixed permutation. For d=1,2,3,4,...,10 these are A000045, A002524, A002526, A072856, A154654, A154655, A154656, A154657, A154658, A154659. The generating function is a rational function f_d(z)/g_d(z) (see the Kløve report referenced here). For d<=6, deg g_d = 2^{d-1} + binomial(2*d,d)/2 and deg f_d(z) = deg g_d(z)-2d. As a table:

%C    d deg g_d deg f_d

%C    1    2       0

%C    2    5       1

%C    3   14       8

%C    4   43      35

%C    5  142     132

%C    6  494     482

%C (End)

%C For positive n, a(n) equals the permanent of the n X n matrix with 1's along the five central diagonals, and 0's everywhere else. - _John M. Campbell_, Jul 09 2011

%D 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.

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

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

%D R. P. Stanley, Enumerative Combinatorics I, Example 4.7.16, p. 253.

%H R. H. Hardin, <a href="/A002524/b002524.txt">Table of n, a(n) for n = 0..400</a>, Jul 11 2010

%H V. Baltic, <a href="http://dx.doi.org/10.2298/AADM1000008B">On the number of certain types of strongly restricted permutations</a>, Appl. An. Disc. Math. 4 (2010), 119-135; DOI:10.2298/AADM1000008B.

%H M. Barnabei, F. Bonetti and M. Silimbani, <a href="https://doi.org/10.37236/2556">Two permutation classes related to the Bubble Sort operator</a>, Electronic Journal of Combinatorics 19(3) (2012), #P25. - From _N. J. A. Sloane_, Dec 25 2012

%H Fan R. K. Chung, Persi Diaconis, and Ron Graham, <a href="https://statweb.stanford.edu/~cgates/PERSI/papers/sequential_sampling_10.pdf">Permanental generating functions and sequential importance sampling</a>, Stanford University (2018).

%H Torleiv Kløve, <a href="http://www.ii.uib.no/publikasjoner/texrap/pdf/2008-376.pdf">Spheres of Permutations under the Infinity Norm - Permutations with limited displacement</a>, Reports in Informatics, Department of Informatics, University of Bergen, Norway, no. 376, November 2008.

%H Torleiv Kløve, <a href="https://doi.org/10.37236/193">Generating functions for the number of permutations with limited displacement</a>, Electron. J. Combin., 16 (2009), #R104. - From _N. J. A. Sloane_, May 04 2011.

%H O. Krafft and M. Schaefer, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/40-5/krafft.pdf">On the number of permutations within a given distance</a>, Fib. Quart. 40 (5) (2002) 429-434.

%H Ting Kuo, <a href="http://www.csroc.org.tw/journal/JOC25-2/JOC25-2-4.pdf">K-sorted Permutations with Weakly Restricted Displacements</a>, Journal of Computers, 2014. See p. 36.

%H R. Lagrange, <a href="http://archive.numdam.org/article/ASENS_1962_3_79_3_199_0.pdf">Quelques résultats dans la métrique des permutations</a>, Annales Scientifiques de l'École Normale Supérieure, Paris, 79 (1962), 199-241.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.

%H Andrew Tsao, <a href="https://purl.stanford.edu/kq800hs0924">Sampling Methodology for Intractable Counting Problems</a>, Ph. D. Thesis, Stanford University (2020).

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,2,0,-1).

%F G.f.: (1-x)/(1-2*x-2*x^3+x^5). - _Simon Plouffe_ in his 1992 dissertation.

%t CoefficientList[Series[(1-x)/(1-2*x-2*x^3+x^5), {x,0,50}], x] (* _Vladimir Joseph Stephan Orlovsky_, Jun 24 2011 *)

%o (PARI) a(n)=if(n,([0,1,0,0,0; 0,0,1,0,0; 0,0,0,1,0; 0,0,0,0,1; -1,0,2,0,2]^n*[1;1;2;6;14])[1,1],1) \\ _Charles R Greathouse IV_, Jul 28 2015

%o (Magma) I:=[1,1,2,6,14]; [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 21 2022

%o (Sage) [( (1-x)/(1-2*x-2*x^3+x^5) ).series(x,n+1).list()[n] for n in (0..40)] # _G. C. Greubel_, Jan 21 2022

%Y Column k=2 of A306209.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_

%E Typo in comment corrected by _Vaclav Kotesovec_, Dec 01 2012