A186144 -id:A186144 - cp's OEIS frontend

A039745 Diameter of symmetric group S_n when generated by (1,2) and (1,2,3,...,n).

0, 1, 2, 6, 11, 18, 25, 35, 45, 58, 71, 87, 103, 122, 141

Offset: 1

a(n) is smallest number such that every element of S_n can be written as a product of at most a(n) terms each of which is the transposition (1,2) or the n-cycle (1,2,3,...,n).

The distinction between A039745 (this sequence) and A186783 comes from whether we treat the Cayley graph of the generating set as directed or undirected (alternatively, whether we allow multiplication by inverses of generators when constructing elements). A039745 deals with the directed Cayley graph, while A186783 deals with the undirected one. - Max Alekseyev, Sep 09 2011

			a(3)=2 because (1,3,2) = (1,2,3)(1,2).

Dmytro Fedoriaka, Growth function for n=15.

Cf. A378881 (antipodal permutations), A186144 (number of them).

Cf. A186783 (LRE diameter).

a[n_] := GraphDiameter[CayleyGraph[SymmetricGroup[n]]] (* Ben Whitmore, Nov 13 2020 *)

def a(n): return PermutationGroup([[(1,2)],[tuple(1..n)]]).cayley_graph().diameter() # Max Alekseyev, Mar 02 2010

a(12)-a(13) by Ben Whitmore, Nov 12 2020
a(14) by Dmytro Fedoriaka, Jun 30 2025
a(15) by Dmytro Fedoriaka, Jul 14 2025

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.

cp's OEIS Frontend

A039745 Diameter of symmetric group S_n when generated by (1,2) and (1,2,3,...,n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Sage

Extensions