|
| |
|
|
A111111
|
|
Number of simple permutations of degree n.
|
|
3
| |
|
|
1, 2, 0, 2, 6, 46, 338, 2926, 28146, 298526, 3454434, 43286526, 583835650, 8433987582, 129941213186, 2127349165822, 36889047574274, 675548628690430, 13030733384956418, 264111424634864638
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| A permutation is simple if the only intervals that are fixed are the singletons and [1..n].
For example, the permutation
1234567
2647513
is not simple since it maps [2..5] onto [4..7].
In other words, a permutation [1 ... n] -> [p_1 p_2 ... p_n] is simple if there is no string of consecutive numbers [i_1 ... i_k] which is mapped onto a string of consecutive numbers [p_i_1 ... p_i_k] except for the strings of length k = 1 or n.
|
|
|
REFERENCES
| M. H. Albert and M. D. Atkinson, Simple permutations and pattern restricted permutations, Discr. Math., 300 (2005), 1-15.
M. H. Albert, M. D. Atkinson and M. Klazar, The enumeration of simple permutations, Journal of Integer Sequences 6 (2003), Article 03.4.4, 18 pages.
R. Brignall et al., Decomposing simple permutations with enumerative consequences, Combinatorica, 28 (2008), 385-400.
Corteel, Sylvie; Louchard, Guy; and Pemantle, Robin, Common intervals of permutations. in Mathematics and Computer Science. III, 3--14, Trends Math., Birkhuser, Basel, 2004.
Corteel, Sylvie; Louchard, Guy; and Pemantle, Robin, Common intervals in permutations, Discrete Math. Theor. Comput. Sci. 8 (2006), no. 1, 189-216.
|
|
|
LINKS
| T. D. Noe, Table of n, a(n) for n = 1..100
|
|
|
FORMULA
| a(n)=-A059372(n)+2(-1)^(n+1) - assuming offset=1 in A059372
a(n) ~ n!*(1-4/n)/e^2 - Jon Schoenfield, Aug 05 2006
|
|
|
EXAMPLE
| The simple permutations of lowest degree are 1, 12, 21, 2413, 3142.
|
|
|
CROSSREFS
| Cf. A059372.
Sequence in context: A161803 A057980 A081081 * A185343 A161014 A154852
Adjacent sequences: A111108 A111109 A111110 * A111112 A111113 A111114
|
|
|
KEYWORD
| nonn,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com), Oct 14 2005
|
| |
|
|
