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,2

Links

Table of n, a(n) for n=1..38.

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).

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

Cf. A000292, A228393.

Sequence in context: A335537 A150276 A189043 * A190910 A150277 A150278

Adjacent sequences: A228389 A228390 A228391 * A228393 A228394 A228395

Keyword

nonn,easy

Author

Vincent Vatter, Aug 21 2013

Status

approved