|
| |
|
|
A002524
|
|
Number of permutations of length n within distance 2 of a fixed permutation.
(Formerly M1600 N0626)
|
|
77
| |
|
|
1, 1, 2, 6, 14, 31, 73, 172, 400, 932, 2177, 5081, 11854, 27662, 64554, 150639, 351521, 820296, 1914208, 4466904, 10423761, 24324417, 56762346, 132458006, 309097942, 721296815, 1683185225, 3927803988, 9165743600, 21388759708, 49911830577, 116471963129
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Comment from Torleiv Klove, Jan 09 2009: (Start)
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
Klove 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)
For positive n, a(n) equals the permanent of the nXn matrix with 1's along the five central diagonals, and 0's everywhere else. [From John M. Campbell, Jul 09 2011]
|
|
|
REFERENCES
| T. Klove, Generating functions for the number of permutations with limited displacement, Electron. J. Combin., 16 (2009), #R104. - From N. J. A. Sloane, May 04 2011.
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.
|
|
|
LINKS
| R. H. Hardin, Table of n, a(n) for n=0..400, Jul 11 2010
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.
|
|
|
FORMULA
| G.f.: (1-x)/(1-2*x-2*x^3+x^5). - N. J. A. Sloane, May 04 2011.
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
|
|
|
MAPLE
| A002524:=-(-1+z)/(1-2*z-2*z**3+z**5); [S. Plouffe in his 1992 dissertation.]
|
|
|
MATHEMATICA
| CoefficientList[Series[(1 - z)/(z^5 - 2 z^3 - 2 z + 1), {z, 0, 100}], z] (* From Vladimir Joseph Stephan Orlovsky, Jun 24 2011 *)
|
|
|
CROSSREFS
| Sequence in context: A095121 A122959 A059076 * A188493 A055292 A035592
Adjacent sequences: A002521 A002522 A002523 * A002525 A002526 A002527
|
|
|
KEYWORD
| nonn,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Removed attribute "conjectured" from Plouffe g.f. Commented Mallows g.f R. J. Mathar (mathar(AT)strw.leidenuniv.nl), Mar 11 2009
|
| |
|
|
