A228394 The number of permutations of length n sortable by 2 prefix block transpositions.
1, 2, 6, 21, 61, 146, 302, 561, 961, 1546, 2366, 3477, 4941, 6826, 9206, 12161, 15777, 20146, 25366, 31541, 38781, 47202, 56926, 68081, 80801, 95226, 111502, 129781, 150221, 172986, 198246, 226177, 256961, 290786, 327846, 368341, 412477, 460466, 512526, 568881
Offset: 1
Examples
There are 3 permutations of length 4 that cannot be sorted by 2 prefix block transpositions.
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
- Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).
Programs
-
Mathematica
CoefficientList[Series[(1/x) (-1 - (x^2 + 1) (6 x^2 - 4 x + 1)/(x - 1)^5), {x, 0, 50}], x] (* Bruno Berselli, Aug 22 2013 *) LinearRecurrence[{5,-10,10,-5,1},{1,2,6,21,61},40] (* Harvey P. Dale, May 28 2018 *)
Formula
G.f.: -1 -(x^2 + 1)*(6*x^2 - 4*x + 1)/(x - 1)^5.
a(n) = 1 + (n-1)*n*(3*n^2-11*n+16)/12. [Bruno Berselli, Aug 22 2013]