login
A228392
The number of permutations of length n sortable by 2 block transpositions.
1
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,2
LINKS
V. Bafna and P.A. Pevzner, Sorting by transpositions, SIAM J. Discrete Math. 11, 2 (1998), 224-240.
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv:1308.4946 [math.CO], 2013.
FORMULA
G.f.: -1 -(x^6 - 2*x^5 + 23*x^4 - 22*x^3 + 16*x^2 - 6*x + 1)/(x - 1)^7.
EXAMPLE
The shortest permutation which cannot be sorted by 2 block transpositions is of length 4.
PROG
(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
CROSSREFS
Sequence in context: A335537 A150276 A189043 * A190910 A150277 A150278
KEYWORD
nonn,easy
AUTHOR
Vincent Vatter, Aug 21 2013
STATUS
approved