login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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: A150275 A150276 A189043 * A190910 A150277 A150278

Adjacent sequences:  A228389 A228390 A228391 * A228393 A228394 A228395

KEYWORD

nonn,easy

AUTHOR

Vincent Vatter, Aug 21 2013

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 20 21:07 EDT 2019. Contains 327247 sequences. (Running on oeis4.)