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,2

Links

Table of n, a(n) for n=1..40.

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).

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]

Example

There are 3 permutations of length 4 that cannot be sorted by 2 prefix block transpositions.

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 *)

Crossrefs

Cf. A000124, A228395.

Sequence in context: A104143 A088812 A228398 * A245749 A342440 A001434

Adjacent sequences: A228391 A228392 A228393 * A228395 A228396 A228397

Keyword

nonn,easy

Author

Vincent Vatter, Aug 21 2013

Status

approved