A228393 The number of permutations of length n that can be sorted by 3 block transpositions.
1, 2, 6, 24, 120, 675, 3527, 15484, 56917, 179719, 500864, 1260117, 2913132, 6274230, 12726573, 24521243, 45190897, 80108200, 137224138, 228026582, 368765112, 581994117, 898492563, 1359625566, 2020220021, 2952034021, 4247907652, 6026690971, 8439053564
Offset: 1
Examples
The shortest permutations which cannot be sorted by 3 block transpositions are of length 6.
Links
- V. Bafna and P.A. Pevzner, Sorting by transpositions, SIAM J. Discrete Math. 11, 2 (1998), 224-240.
- Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv:1410.2657 [math.CO], 2014.
- C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv:1308.4946 [math.CO], 2013.
- Index entries for linear recurrences with constant coefficients, signature (10,-45,120,-210,252,-210,120,-45,10,-1).
Programs
-
Mathematica
CoefficientList[Series[-(x^9 - 9 x^8 - 17 x^7 - 263 x^6 - 3 x^5 - 120 x^4 + 66 x^3 - 31 x^2 + 8 x - 1)/(x - 1)^10, {x, 0, 40}], x] (* Bruno Berselli, Aug 22 2013 *)
Formula
G.f.: -x*(x^9 - 9*x^8 - 17*x^7 - 263*x^6 - 3*x^5 - 120*x^4 + 66*x^3 - 31*x^2 + 8*x - 1)/(x - 1)^10.