A228395 The number of permutations of length n sortable by 3 prefix block transpositions.
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
Examples
The shortest permutations which cannot be sorted by 3 prefix block transpositions are of length 5.
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.
Programs
-
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
-
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
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]