cp's OEIS Frontend

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