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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A260695 a(n) is the number of permutations p of {1,..,n} such that the minimum number of block interchanges required to sort the permutation p to the identity permutation is maximized. 0
1, 1, 5, 8, 84, 180, 3044, 8064, 193248, 604800 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

LINKS

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

D. A. Christie, Sorting Permutations by Block-Interchanges, Inf. Process. Lett. 60 (1996), 165-169.

EXAMPLE

The next three lines illustrate applying block interchanges to [2 4 6 1 3 5 7], an element of S_7.

Step 1: [2 4 6 1 3 5 7]->[3 5 1 2 4 6 7]-interchange blocks 3 5 and 2 4 6.

Step 2: [3 5 1 2 4 6 7]->[4 1 2 3 5 6 7]-interchange blocks 3 5 and 4.

Step 3: [4 1 2 3 5 6 7]->[1 2 3 4 5 6 7]-interchange blocks 4 and 1 2 3.

As [2 4 6 1 3 5 7] requires 3 = floor(7/2) block interchanges, it is one of the a(7) = 3044.

Each of the 23 non-identity elements of S_4 requires at least 1 block interchange to sort to the identity. But only 8 of these require 2 block interchanges, the maximum number required for elements of S_4. They are: [4 3 2 1], [4 1 3 2], [4 2 1 3], [3 1 4 2], [3 2 4 1], [2 4 1 3], [2 1 4 3], [2 4 3 1]. So, a(4) = 8.

CROSSREFS

The following sequences give the number of elements of S_n that can be sorted by .. a single block interchange (A145126), two block interchanges (A228401), three block interchanges (A256181), context directed block interchanges (A249165).

The following sequences give the number of signed permutations that can be sorted by .. context directed reversals (A260511), applying either context directed reversals or context directed block interchanges (A260506).

Sequence in context: A213239 A123819 A286076 * A153720 A101016 A264295

Adjacent sequences:  A260692 A260693 A260694 * A260696 A260697 A260698

KEYWORD

nonn,more

AUTHOR

Marion Scheepers, Nov 16 2015

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified November 23 19:08 EST 2017. Contains 295128 sequences.