|
|
A111111
|
|
Number of simple permutations of degree n.
|
|
12
|
|
|
1, 2, 0, 2, 6, 46, 338, 2926, 28146, 298526, 3454434, 43286526, 583835650, 8433987582, 129941213186, 2127349165822, 36889047574274, 675548628690430, 13030733384956418, 264111424634864638, 5612437196153963522, 124789500579376435198, 2897684052921851965442
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
A permutation is simple if the only intervals that are mapped onto intervals 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
|
Corteel, Sylvie; Louchard, Guy; and Pemantle, Robin, Common intervals of permutations. in Mathematics and Computer Science. III, 3--14, Trends Math., Birkhuser, Basel, 2004.
S. Kitaev, Patterns in Permutations and Words, Springer-Verlag, 2011. see p. 399 Table A.7
Bridget Eileen Tenner, Interval posets of permutations, arXiv:2007.06142, Aug 2021.
|
|
LINKS
|
|
|
FORMULA
|
a(n) ~ n!*exp(-2)*(1 - 4/n + 2/(n*(n-1)) - (40/3)/(n*(n-1)*(n-2)) - ...). Coefficients are given by A280780(n)/A280781(n).- Gheorghe Coserea, Jan 23 2017
|
|
EXAMPLE
|
G.f. = x + 2*x^2 + 2*x^4 + 6*x^5 + 46*x^6 + 338*x^7 + 2926*x^8 + ...
The simple permutations of lowest degree are 1, 12, 21, 2413, 3142.
|
|
MATHEMATICA
|
nmax = 20; t[n_, k_] := t[n, k] = Sum[(m + 1)!*t[n - m - 1, k - 1], {m, 0, n - k}]; t[n_, 1] = n!; t[n_, n_] = 1; tnk = Table[t[n, k], {n, 1, nmax}, {k, 1, nmax}]; A111111 = -Inverse[tnk][[All, 1]] + 2*(-1)^Range[0, nmax - 1]; A111111[[2]] = 2;
|
|
PROG
|
(PARI) simple(v)=for(i=1, #v-1, for(j=i+1, #v, my(u=vecsort(v[i..j])); if(u[#u]-u[1]==#u-1 && #u<#v, return(0)))); 1
seq(N) = Vec(2 + 2*x^2 - 2/(1+x) - serreverse(x*Ser(vector(N, n, n!)))); \\ Gheorghe Coserea, Jan 22 2017
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Incorrect statement removed by Jay Pantone, Jul 16 2014
|
|
STATUS
|
approved
|
|
|
|