|
%I #25 Apr 03 2015 17:56:56
%S 1,2,6,24,118,534,1851,5158,12264,25943,50214,90656,154758,252304,
%T 395793,600894,886936,1277433,1800644,2490168,3385574,4533066,5986183,
%U 7806534,10064568,12840379,16224546,20319008,25237974,31108868,38073309,46288126,55926408
%N The number of permutations of length n sortable by 3 reversals.
%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 G. A. Watterson, W. J. Ewens, T. E. Hall, and A. Morgan, <a href="http://dx.doi.org/10.1016/0022-5193(82)90384-8">The chromosome inversion problem</a>, Journal of Theoretical Biology, 99 (1982), 1-7.
%F G.f.: -1 -(2*x^10 + 5*x^9 + 12*x^8 - 75*x^7 + 58*x^6 + 20*x^5 + 24*x^4 - 22*x^3 + 16*x^2 - 6*x + 1)/(x - 1)^7.
%F a(n) = n! for 0 < n < 4; for n > 3, a(n) = 318 + n*(7*n^5 -21*n^4 -125*n^3 -819*n^2 +12862*n -42720)/144. [_Bruno Berselli_, Aug 22 2013]
%e There are 2 permutations of length 5 which cannot be sorted by 3 reversals.
%t CoefficientList[Series[(1/x) (-1 - (2 x^10 + 5 x^9 + 12 x^8 - 75 x^7 + 58 x^6 + 20 x^5 + 24 x^4 - 22 x^3 + 16 x^2 - 6 x + 1)/(x - 1)^7), {x, 0, 50}], x] (* _Bruno Berselli_, Aug 22 2013 *)
%Y Cf. A000124, A228396.
%K nonn,easy
%O 1,2
%A _Vincent Vatter_, Aug 21 2013
|
