login
A228395
The number of permutations of length n sortable by 3 prefix block transpositions.
2
1, 2, 6, 24, 116, 521, 1877, 5531, 13939, 31156, 63416, 119802, 213006, 360179, 583871, 913061, 1384277, 2042806, 2943994, 4154636, 5754456, 7837677, 10514681, 13913759, 18182951, 23491976, 30034252, 38029006, 47723474, 59395191, 73354371, 89946377
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, 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
Sequence in context: A369766 A211321 A242820 * A082631 A212198 A182216
KEYWORD
nonn,easy
AUTHOR
Vincent Vatter, Aug 21 2013
STATUS
approved