A228394 - OEIS

%I #27 May 28 2018 20:07:54

%S 1,2,6,21,61,146,302,561,961,1546,2366,3477,4941,6826,9206,12161,

%T 15777,20146,25366,31541,38781,47202,56926,68081,80801,95226,111502,

%U 129781,150221,172986,198246,226177,256961,290786,327846,368341,412477,460466,512526,568881

%N The number of permutations of length n sortable by 2 prefix block transpositions.

%H Z. Dias and J. Meidanis, <a href="http://dx.doi.org/10.1007/3-540-45735-6_7">Sorting by prefix transpositions</a>, In Proceedings of the 9th International Symposium on String Processing and Information Retrieval (London, UK, UK, 2002), SPIRE 2002, Springer-Verlag, pp. 65-76.

%H C. Homberger, <a href="http://arxiv.org/abs/1410.2657">Patterns in Permutations and Involutions: A Structural and Enumerative Approach</a>, arXiv preprint 1410.2657, 2014

%H C. Homberger, V. Vatter, <a href="http://arxiv.org/abs/1308.4946">On the effective and automatic enumeration of polynomial permutation classes</a>, arXiv preprint arXiv:1308.4946, 2013

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (5,-10,10,-5,1).

%F G.f.: -1 -(x^2 + 1)*(6*x^2 - 4*x + 1)/(x - 1)^5.

%F a(n) = 1 + (n-1)*n*(3*n^2-11*n+16)/12. [_Bruno Berselli_, Aug 22 2013]

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

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

%t LinearRecurrence[{5,-10,10,-5,1},{1,2,6,21,61},40] (* _Harvey P. Dale_, May 28 2018 *)

%Y Cf. A000124, A228395.

%K nonn,easy

%O 1,2

%A _Vincent Vatter_, Aug 21 2013