|
%I #29 Jan 04 2017 14:09:55
%S 1,2,6,23,89,295,827,2017,4405,8812,16424,28887,48413,77897,121045,
%T 182513,268057,384694,540874,746663,1013937,1356587,1790735,2334961,
%U 3010541,3841696,4855852,6083911,7560533,9324429,11418665,13890977,16794097,20186090,24130702,28697719,33963337,40010543
%N The number of permutations of length n sortable by 2 block transpositions.
%H V. Bafna and P.A. Pevzner, <a href="http://dx.doi.org/10.1137/S089548019528280X">Sorting by transpositions</a>, SIAM J. Discrete Math. 11, 2 (1998), 224-240.
%H Cheyne Homberger, <a href="http://arxiv.org/abs/1410.2657">Patterns in Permutations and Involutions: A Structural and Enumerative Approach</a>, arXiv:1410.2657 [math.CO], 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:1308.4946 [math.CO], 2013.
%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (7,-21,35,-35,21,-7,1).
%F G.f.: -1 -(x^6 - 2*x^5 + 23*x^4 - 22*x^3 + 16*x^2 - 6*x + 1)/(x - 1)^7.
%e The shortest permutation which cannot be sorted by 2 block transpositions is of length 4.
%o (PARI) Vec(-1-(x^6-2*x^5+23*x^4-22*x^3+16*x^2-6*x+1)/(x-1)^7 + O(x^50)) \\ _Michel Marcus_, Apr 03 2015
%Y Cf. A000292, A228393.
%K nonn,easy
%O 1,2
%A _Vincent Vatter_, Aug 21 2013
|
