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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A228394 The number of permutations of length n sortable by 2 prefix block transpositions. 0
1, 2, 6, 21, 61, 146, 302, 561, 961, 1546, 2366, 3477, 4941, 6826, 9206, 12161, 15777, 20146, 25366, 31541, 38781, 47202, 56926, 68081, 80801, 95226, 111502, 129781, 150221, 172986, 198246, 226177, 256961, 290786, 327846, 368341, 412477, 460466, 512526, 568881 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

LINKS

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

Z. Dias and J. Meidanis, Sorting by prefix transpositions, In Proceedings of the 9th International Symposium on String Processing and Information Retrieval (London, UK, UK, 2002), SPIRE 2002, Springer-Verlag, pp. 65-76.

C. Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657, 2014

C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946, 2013

Index entries for linear recurrences with constant coefficients, signature (5,-10,10,-5,1).

FORMULA

G.f.: -1 -(x^2 + 1)*(6*x^2 - 4*x + 1)/(x - 1)^5.

a(n) = 1 + (n-1)*n*(3*n^2-11*n+16)/12. [Bruno Berselli, Aug 22 2013]

EXAMPLE

There are 3 permutations of length 4 that cannot be sorted by 2 prefix block transpositions.

MATHEMATICA

CoefficientList[Series[(1/x) (-1 - (x^2 + 1) (6 x^2 - 4 x + 1)/(x - 1)^5), {x, 0, 50}], x] (* Bruno Berselli, Aug 22 2013 *)

LinearRecurrence[{5, -10, 10, -5, 1}, {1, 2, 6, 21, 61}, 40] (* Harvey P. Dale, May 28 2018 *)

CROSSREFS

Cf. A000124, A228395.

Sequence in context: A104143 A088812 A228398 * A245749 A001434 A119098

Adjacent sequences:  A228391 A228392 A228393 * A228395 A228396 A228397

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 April 21 10:03 EDT 2019. Contains 322328 sequences. (Running on oeis4.)