A039745 -id:A039745 - cp's OEIS frontend

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

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

A378881 Irregular triangle listing permutations of {1,...,m} which are at maximum distance from the identity permutation under steps rotate left (L) or exchange first two elements (E).

Original entry on oeis.org

1, 2, 1, 1, 3, 2, 3, 1, 2, 3, 2, 1, 2, 1, 4, 3, 2, 3, 1, 4, 2, 4, 3, 1, 1, 2, 5, 3, 4, 2, 1, 5, 3, 4, 3, 1, 6, 5, 4, 2, 2, 1, 7, 6, 3, 5, 4, 2, 1, 7, 6, 4, 3, 5, 3, 1, 8, 7, 6, 5, 4, 2, 2, 1, 9, 8, 7, 3, 6, 5, 4, 2, 1, 9, 8, 7, 5, 4, 3, 6, 3, 1, 10, 9, 8, 7, 6, 5, 4, 2

Offset: 1

Kevin Ryde, Dec 09 2024

Permutations are listed for successive m >= 1 and in lexicographic order for multiple permutations in each m.
The maximum distance is A039745(m) and there may be multiple permutations at that distance.
The number of permutations at the maximum distance is A186144(m). - Pontus von Brömssen, Dec 12 2024

			Triangle begins:
       k=1  2  3  4  5
  n=1:   1
  n=2:   2, 1
  n=3:   1, 3, 2
  n=4:   3, 1, 2
  n=5:   3, 2, 1
  n=6:   2, 1, 4, 3
  n=7:   2, 3, 1, 4
  n=8:   2, 4, 3, 1
  n=9:   1, 2, 5, 3, 4
  n=10:  2, 1, 5, 3, 4
For m=10 there is a single permutation at distance A039745(10) = 58, being row n=17,
  3,1, 10,9,8,7,6,5,4, 2
This shows a pattern seen in even m ranging 6 <= m <= 12 where elements 2 and 3 are exchanged in what would otherwise be decreasing elements (with wrap-around).
For m=11 there are two permutations at distance A039745(11) = 71, being rows n=18 and n=19,
  2,1, 11,10,9,8, 3,7,6,5,4
  2,1, 11,10,9,8, 6,5,4,3,7
                  \-------/
These show a pattern seen in odd m ranging 7 <= m <= 13 where the final (m-1)/2 elements are rotated left and right from what would otherwise be decreasing elements (with wrap-around).

Kevin Ryde, Table of n, a(n) for rows 1..22 (m=1..13)

Cf. A039745, A186144.

A186144 Number of elements in the symmetric group S_n whose distance from a fixed element is the group diameter under compositions of (1,2) and (1,2,...,n).

Original entry on oeis.org

1, 1, 3, 3, 2, 1, 2, 1, 2, 1, 2, 1, 2

Offset: 1

Tony Bartoletti, Feb 23 2011

a(n) is the number of elements in the symmetric group S_n that are maximally distant from any fixed element, where distance is taken to be the minimal sequence of operations composed from transposition (1,2) and rotation (1,2,...,n) producing one element from another. This maximal distance is the diameter of S_n under the stated compositions, given by A039745(n).
From Ben Whitmore, Nov 14 2020: (Start)
Conjecture (verified up to n = 13): Consider the a(n) permutations that take A039745(n) steps to reach the identity. For odd n>5, we have a(n) = 2 and the actions of these permutations on the list [1, 2, ..., n] are
[2, 1, (n+3)/2, n, n-1, ..., (n+5)/2, (n+1)/2, (n-1)/2, ..., 4, 3],
[2, 1, n-1, n-2, ..., (n+3)/2, n, (n+1)/2, (n-1)/2, ..., 4, 3],
and for even n>5, we have a(n) = 1 and the action of the permutation is
[2, n, 1, n-1, n-2, ..., 4, 3].
(End)

Cf. A039745, A378881.

Conjecture: For n>4, a(n) = 1 if n is even, a(n) = 2 if n is odd. - Ben Whitmore, Nov 14 2020

a(10)-a(13) by Ben Whitmore, Nov 14 2020

cp's OEIS Frontend

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

A378881 Irregular triangle listing permutations of {1,...,m} which are at maximum distance from the identity permutation under steps rotate left (L) or exchange first two elements (E).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A186144 Number of elements in the symmetric group S_n whose distance from a fixed element is the group diameter under compositions of (1,2) and (1,2,...,n).

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions