0,3

Comment from Torleiv Klove, Jan 09 2009: (Start)

Let V(d,n) be the number of permutations of length n within distance d.

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

report referenced here). For d<=6,

deg g_d=2^{n-1}+binomial(2*d,d)/2 and deg f_d(z)=deg g_d(z)-2d.

As a table:

d deg g_d deg f_d

1 2 0

2 5 1

3 14 8

4 43 35

5 142 132

6 494 482

(End)

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. H. Lehmer, Permutations with strongly restricted displacements. Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), pp. 755-770. North-Holland, Amsterdam, 1970.

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

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

Torleiv Klove, 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 re'sultats dans la me'trique des permutations, Annales Scientifiques de l'\'{E}cole Normale Sup\'{e}rieure, Paris, 79 (1962), 199-241.

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.

S. Plouffe, 1031 Generating Functions and Conjectures, Universit\'{e} du Qu\'{e}bec \`{a} Montr\'{e}al, 1992.

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

A002524:=-(-1+z)/(1-2*z-2*z**3+z**5); [S. Plouffe in his 1992 dissertation.]

Sequence in context: A122958 A122959 A059076 this_sequence A055292 A035592 A096238

Adjacent sequences: A002521 A002522 A002523 this_sequence A002525 A002526 A002527

nonn,easy

N. J. A. Sloane (njas(AT)research.att.com).

Removed attribute "conjectured" from Plouffe g.f. Commented Mallows g.f R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Mar 11 2009