|
%I #27 Apr 18 2017 22:46:19
%S 1,2,6,24,116,521,1877,5531,13939,31156,63416,119802,213006,360179,
%T 583871,913061,1384277,2042806,2943994,4154636,5754456,7837677,
%U 10514681,13913759,18182951,23491976,30034252,38029006,47723474,59395191,73354371,89946377
%N The number of permutations of length n sortable by 3 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.
%F G.f.: -1-(59*x^6 + 18*x^5 + 24*x^4 - 22*x^3 + 16*x^2 - 6*x + 1)/(x - 1)^7.
%F a(n) = 1 + (1/24)*(3n^6 - 37n^5 + 184n^4 - 441n^3 + 509n^2 - 218n). [_Ralf Stephan_, Aug 22 2013]
%e The shortest permutations which cannot be sorted by 3 prefix block transpositions are of length 5.
%p 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
%o (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
%Y Cf. A000124, A228395.
%K nonn,easy
%O 1,2
%A _Vincent Vatter_, Aug 21 2013
|
