%I A002524 M1600 N0626
%S A002524 1,1,2,6,14,31,73,172,400,932,2177,5081,11854,27662,64554,
%T A002524 150639,351521,820296,1914208,4466904,10423761,24324417,
%U A002524 56762346,132458006,309097942,721296815,1683185225,3927803988
%N A002524 Number of permutations of length n within distance 2.
%C A002524 Comment from Torleiv Klove, Jan 09 2009: (Start)
%C A002524 Let V(d,n) be the number of permutations of length n within distance 
               d.
%C A002524 For d=1,2,3,4,...,10 these are A000045, A002524, A002526,
%C A002524 A072856, A154654, A154655, A154656, A154657, A154658, A154659.
%C A002524 The generating function is a rational function f_d(z)/g_d(z) (see the
%C A002524 report referenced here). For d<=6,
%C A002524 deg g_d=2^{n-1}+binomial(2*d,d)/2 and deg f_d(z)=deg g_d(z)-2d.
%C A002524 As a table:
%C A002524 d deg g_d deg f_d
%C A002524 1 2 0
%C A002524 2 5 1
%C A002524 3 14 8
%C A002524 4 43 35
%C A002524 5 142 132
%C A002524 6 494 482
%C A002524 (End)
%D A002524 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, 
               Academic Press, 1995 (includes this sequence).
%D A002524 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 
               (includes this sequence).
%D A002524 S. Plouffe, Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques 
               Conjectures, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 
               1992.
%D A002524 R. Lagrange, Quelques re'sultats dans la me'trique des permutations, 
               Annales Scientifiques de l'\'{E}cole Normale Sup\'{e}rieure, Paris, 
               79 (1962), 199-241.
%D A002524 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 A002524 R. P. Stanley, Enumerative Combinatorics I, Example 4.7.16, p. 253.
%H A002524 S. Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">
               Approximations de S\'{e}ries G\'{e}n\'{e}ratrices et Quelques Conjectures</
               a>, Dissertation, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 
               1992.
%H A002524 S. Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">
               1031 Generating Functions and Conjectures</a>, Universit\'{e} du 
               Qu\'{e}bec \`{a} Montr\'{e}al, 1992.
%H A002524 R. Lagrange, <a href="http://archive.numdam.org/article/ASENS_1962_3_79_3_199_0.pdf">
               Quelques re'sultats dans la me'trique des permutations</a>, Annales 
               Scientifiques de l'\'{E}cole Normale Sup\'{e}rieure, Paris, 79 (1962), 
               199-241.
%H A002524 Torleiv Klove, <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.
%F A002524 G.f.: (1+2x^2-x^4)/(1-2x-2x^3+x^5), gives sequence without first 1. - 
               Colin Mallows (colinm(AT)research.avayalabs.com), Aug 15 2002
%p A002524 A002524:=-(-1+z)/(1-2*z-2*z**3+z**5); [S. Plouffe in his 1992 dissertation.]
%Y A002524 Sequence in context: A122958 A122959 A059076 this_sequence A055292 A035592 
               A096238
%Y A002524 Adjacent sequences: A002521 A002522 A002523 this_sequence A002525 A002526 
               A002527
%K A002524 nonn,easy
%O A002524 0,3
%A A002524 N. J. A. Sloane (njas(AT)research.att.com).
%E A002524 Removed attribute "conjectured" from Plouffe g.f. Commented Mallows g.f 
               R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Mar 11 2009