A228392 The number of permutations of length n sortable by 2 block transpositions.
1, 2, 6, 23, 89, 295, 827, 2017, 4405, 8812, 16424, 28887, 48413, 77897, 121045, 182513, 268057, 384694, 540874, 746663, 1013937, 1356587, 1790735, 2334961, 3010541, 3841696, 4855852, 6083911, 7560533, 9324429, 11418665, 13890977, 16794097, 20186090, 24130702, 28697719, 33963337, 40010543
Offset: 1
Examples
The shortest permutation which cannot be sorted by 2 block transpositions is of length 4.
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 (7,-21,35,-35,21,-7,1).
Programs
-
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
Formula
G.f.: -1 -(x^6 - 2*x^5 + 23*x^4 - 22*x^3 + 16*x^2 - 6*x + 1)/(x - 1)^7.