OFFSET
1,2
LINKS
Z. Dias and J. Meidanis, Sorting by prefix transpositions, In Proceedings of the 9th International Symposium on String Processing and Information Retrieval (London, UK, UK, 2002), SPIRE 2002, Springer-Verlag, pp. 65-76.
C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657, 2014.
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946, 2013.
FORMULA
G.f.: -1-(59*x^6 + 18*x^5 + 24*x^4 - 22*x^3 + 16*x^2 - 6*x + 1)/(x - 1)^7.
a(n) = 1 + (1/24)*(3n^6 - 37n^5 + 184n^4 - 441n^3 + 509n^2 - 218n). [Ralf Stephan, Aug 22 2013]
EXAMPLE
The shortest permutations which cannot be sorted by 3 prefix block transpositions are of length 5.
MAPLE
A228395:=n->1 + (1/24)*(3*n^6 - 37*n^5 + 184*n^4 - 441*n^3 + 509*n^2 - 218*n): seq(A228395(n), n=1..50); # Wesley Ivan Hurt, Apr 18 2017
PROG
(PARI) Vec(-1-(59*x^6+18*x^5+24*x^4-22*x^3+16*x^2-6*x+1)/(x-1)^7 + O(x^50)) \\ Michel Marcus, Apr 03 2015
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Vincent Vatter, Aug 21 2013
STATUS
approved