A186752 -id:A186752 - cp's OEIS frontend

A048200 Minimal length pair-exchange / set-rotate sequence to reverse n distinct ordered elements.

0, 1, 2, 4, 10, 15, 23, 32, 42, 55, 67, 84, 98, 119

Offset: 1

"Rotate" is always a left-rotate (moves leftmost element to the right end) and "Exchange" is always a pair-exchange of the two leftmost elements.

a(15)<=135 and a(16)<=160. See example solutions in the links section. - Dmitry Kamenetsky, Jun 19 2025

			a(4) = 4 since "xrrx" is the shortest sequence reversing "ABCD". Explicitly, (begin) ABCD, (x)-> BACD, (r)-> ACDB, (r) -> CDBA, (x)-> DCBA.

Danilo Bazzanella, Antonio Di Scala, Simone Dutto, and Nadir Murru, Primality tests, linear recurrent sequences and the Pell equation, arXiv:2002.08062 [math.NT], 2020.
Sean A. Irvine, Java program (github)
Dmitry Kamenetsky, Best known solutions for n <= 16.
Sai Satwik Kuppili, C++ program for generating the moves for a given n
Sai Satwik Kuppili and Bhadrachalam Chitturi, Exact upper bound for sorting R_n with LE, University of Texas at Dallas (2019).
Sai Satwik Kuppili and Bhadrachalam Chitturi, An upper bound for sorting R_n with LRE, arXiv:2002.07342 [cs.DS], 2020.
Sai Satwik Kuppili and Bhadrachalam Chitturi, Exact upper bound for sorting R_n with LE, Discrete Mathematics, Algorithms and Applications, 2020.
Kevin Ryde, C Code

Cf. A058986, A065603, A186752.

C
```
/* See links. */
```
Java
```
/* See links. */
```

Conjecture: a(n) = (3*n^2/4)-2*n if n is even and a(n) = (3*n^2-10*n+15)/4 if n is odd. See links for more information. - Sai Satwik Kuppili and Bhadrachalam Chitturi, Jun 09 2020

a(11) added by Sai Satwik Kuppili and Srinath T, Bhadrachalam Chitturi, Jan 02 2019
a(12) from Sean A. Irvine, Jun 04 2021
a(13) from Kevin Ryde, Dec 19 2024
a(14) from Zachary DeStefano, Jan 03 2025

A186783 Diameter of the symmetric group S_n when generated by the transposition (1,2) and both left and right rotations by (1,2,...,n).

Original entry on oeis.org

0, 1, 2, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78

Offset: 1

Tony Bartoletti, Feb 26 2011

Given an ordered sequence of n elements (1,2,3,...,n), let X represent the permutation that transposes the first two elements, X(1,2,3,...,n) = (2,1,3,...,n), let L be the "left rotation" of the sequence, L(1,2,3,...,n) = (2,3,...,n,1), and let R be the "right rotation", R(1,2,3,...,n) = (n,1,2,...,n-1). Then every permutation of (1,2,3,...,n) can be expressed as a composition of the permutations X, L and R. One can exhaustively generate such compositions by taking L="0", X="1", R="2", and considering, in turn, base 3 numbers of increasing length (padded with leading zeros). Note that any base 3 number containing the subsequence "11", "02" or "20" may be discarded.
Note also that by defining the distance between any two permutations p and q in S_n, dist(p,q), to be the length of the minimal composition of LXR transforming p into q, we have dist(p,q) = dist(q,p), owing to L and R being mutually inverse, and X being self-inverse.
Conjecture from Chervov et. al., section 4.2: The longest and unique element of S_n is (1,2)(n,3)(n-1,4)(n-2,5)... = (2,1,n,n-1,n-2,...,3). The conjecture holds for n <= 13. - Dmitry Kamenetsky, Jun 22 2025

			The diameter of S_5 is 10, given this set of generators, since there is no sequence shorter than 0010010121 (i.e., LLXLLXLXRX) that will transform (1,2,3,4,5) into (2,1,5,4,3), and there is no permutation of (1,2,3,4,5) that requires more than a length-10 composition of L, X and R. Thus a(5) = 10.

Danilo Bazzanella, Antonio Di Scala, Simone Dutto, and Nadir Murru, Primality tests, linear recurrent sequences and the Pell equation, arXiv:2002.08062 [math.NT], 2020.
A. Chervov, A. Soibelman, S. Lytkin, et al., CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs, arXiv:2502.18663 [cs.LG], 2025. See pp. 1, 2, 4, 18, 24.
Sai Satwik Kuppili and Bhadrachalam Chitturi, An Upper Bound for Sorting R_n with LRE, arXiv:2002.07342 [cs.DS], 2020.

Cf. A039745, A186752, A000217.

a[1] = 0; a[n_] := GraphDiameter[CayleyGraph[PermutationGroup[{Cycles[{{1, 2}}], Cycles[{Range[n]}], InversePermutation[Cycles[{Range[n]}]]}]]]; (* Ben Whitmore, Jan 09 2018 *)

def a(n): return PermutationGroup([[(1, 2)], [tuple(1..n)], PermutationGroupElement([tuple(1..n)])^(-1)]).cayley_graph().diameter() # Max Alekseyev, Sep 09 2011

Conjecture: a(n) = - Sum_{k=1..n-1} Stirling1(n+k-1, (n-1)*k). This formula holds for all known n. - Arkadiusz Wesolowski, Mar 30 2013. For n>3, this formula contains only one nonzero term (for k=1) and reduces to the formula n*(n-1)/2 conjectured below. - Max Alekseyev, Sep 10 2020
Conjecture: a(n) = n*(n-1)/2 for all n>3. - Per W. Alexandersson, Aug 25 2020
Conjectures from Colin Barker, Aug 26 2020: (Start)
G.f.: x^2*(1 - x + 3*x^2 - 3*x^3 + x^4) / (1 - x)^3.
a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3).
(End)

a(8)=28 added by Tony Bartoletti, Mar 12 2011
a(9)=36 added by R. H. Hardin, Sep 09 2011
a(10)=45 added by Sharon Li, Mar 09 2013
a(11)=55 and a(12)=66 added by James Bieron, Mar 15 2013
a(13)=78 added by Ben Whitmore, Jan 09 2018

A378834 Number of ways to reverse a permutation of n elements by the minimum number of steps of rotate left or right 1 place (L,R), or exchange first two elements (E).

Original entry on oeis.org

1, 3, 2, 2, 2, 6, 6, 32, 32, 240, 240, 2304, 2304

Offset: 1

Kevin Ryde, Dec 09 2024

The minimum number of steps is A186752(n).
For n=2, steps L,R,E all have the same effect but each is taken as a separate way so that a(2) = 3.
For 4 <= n <= 13, a(n) = (h+2)*2^h*h! where h = floor((n-4)/2).

			For n=1, permutation {1} is already its own reversal so has a(1) = 1 way of no steps (A186752(1) = 0).
For n=5, the a(5) = 2 ways to reverse {1,2,3,4,5} by A186752(5) = 8 steps are
  E, L, L, E, L, E, R, E
  E, L, E, R, E, R, R, E
Notice these are inverses: reverse the order and flip L<->R in one makes the other.

Cf. A186752 (number of steps).

Cf. A061545 (ways for LE).

cp's OEIS Frontend

A048200 Minimal length pair-exchange / set-rotate sequence to reverse n distinct ordered elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Java

Formula

Extensions

A186783 Diameter of the symmetric group S_n when generated by the transposition (1,2) and both left and right rotations by (1,2,...,n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Formula

Extensions

A378834 Number of ways to reverse a permutation of n elements by the minimum number of steps of rotate left or right 1 place (L,R), or exchange first two elements (E).

Views

Author

Keywords

Comments

Examples

Crossrefs