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)

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

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

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.

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.

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

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.

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.

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.

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

Adjacent sequences: A002521 A002522 A002523 this_sequence A002525 A002526 A002527

Sequence in context: A122958 A122959 A059076 this_sequence A055292 A035592 A096238

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