|
%I M1671 N0657 #62 Jan 24 2022 07:07:24
%S 1,1,2,6,24,78,230,675,2069,6404,19708,60216,183988,563172,1725349,
%T 5284109,16177694,49526506,151635752,464286962,1421566698,4352505527,
%U 13326304313,40802053896,124926806216,382497958000,1171122069784
%N Number of permutations of length n within distance 3 of a fixed permutation.
%C For positive n, a(n) equals the permanent of the n X n matrix with 1's along the seven 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).
%H R. H. Hardin, <a href="/A002526/b002526.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 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. (Table 3, top row).
%H O. Krafft and M. Schaefer, <a href="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 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 <a href="/index/Rec#order_14">Index entries for linear recurrences with constant coefficients</a>, signature (2,2,0,10,8,-2,-16,-10,-2,4,2,0,2,1).
%F G.f.: (1-x-2*x^2-2*x^4+x^7+x^8)/(1-2*x-2*x^2-10*x^4-8*x^5+2*x^6+16*x^7+10*x^8 +2*x^9-4*x^10-2*x^11-2*x^13-x^14).
%F a(0)=1, a(1)=1, a(2)=2, a(3)=6, a(4)=24, a(5)=78, a(6)=230, a(7)=675, a(8)=2069, a(9)=6404, a(10)=19708, a(11)=60216, a(12)=183988, a(13)=563172, a(n) = 2*a(n-1) +2*a(n-2) +10*a(n-4) +8*a(n-5) -2*a(n-6) -16*a(n-7) -10*a(n-8) -2*a(n-9) +4*a(n-10) +2*a(n-11) +2*a(n-13) +a(n-14). - _Harvey P. Dale_, Jun 22 2011
%t CoefficientList[Series[(1-x-2x^2-2x^4+x^7+x^8)/(1-2x-2x^2-10x^4-8x^5+ 2x^6+ 16x^7+10x^8+2x^9-4x^10-2x^11-2x^13-x^14),{x,0,50}],x] (* or *) LinearRecurrence[{2,2,0,10,8,-2,-16,-10,-2,4,2,0,2,1},{1,1,2,6,24,78, 230, 675,2069,6404,19708,60216,183988,563172},51] (* _Harvey P. Dale_, Jun 22 2011 *)
%o (PARI) Vec((1-x-2*x^2-2*x^4+x^7+x^8)/(1-2*x-2*x^2-10*x^4-8*x^5+2*x^6+16*x^7+10*x^8+2*x^9-4*x^10-2*x^11-2*x^13-x^14)+O(x^99)) \\ _Charles R Greathouse IV_, Jul 16 2011
%o (Magma) R<x>:=PowerSeriesRing(Integers(), 50); Coefficients(R!( (1-x-2*x^2-2*x^4+x^7+x^8)/(1-2*x-2*x^2-10*x^4-8*x^5+2*x^6+16*x^7+10*x^8 +2*x^9-4*x^10-2*x^11-2*x^13-x^14) )); // _G. C. Greubel_, Jan 22 2022
%o (Sage) [( (1-x-2*x^2-2*x^4+x^7+x^8)/(1-2*x-2*x^2-10*x^4-8*x^5+2*x^6+16*x^7+10*x^8 +2*x^9-4*x^10-2*x^11-2*x^13-x^14) ).series(x,n+1).list()[n] for n in (0..40)] # _G. C. Greubel_, Jan 22 2022
%Y The 14 sequences in Kløve's Table 3 are A002526, A002527, A002529, A188379, A188491, A188492, A188493, A188494, A002528, A188495, A188496, A188497, A188498, A002526.
%Y Cf. A002524.
%Y Column k=3 of A306209.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
|
