login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 3
0, 1, 2, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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.

LINKS

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

Danilo Bazzanella, Antonio Di Scala, Simone Dutto, Nadir Murru, Primality tests, linear recurrent sequences and the Pell equation, arXiv:2002.08062 [math.NT], 2020.

Sai Satwik Kuppili, Bhadrachalam Chitturi, An Upper Bound for Sorting R_n with LRE, arXiv:2002.07342 [cs.DS], 2020.

FORMULA

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)

EXAMPLE

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.

MATHEMATICA

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

PROG

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

CROSSREFS

Cf. A039745, A186752, A000217.

Sequence in context: A276211 A190091 A331250 * A133931 A050895 A184426

Adjacent sequences:  A186780 A186781 A186782 * A186784 A186785 A186786

KEYWORD

nonn,more,hard

AUTHOR

Tony Bartoletti, Feb 26 2011

EXTENSIONS

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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 23 03:52 EST 2021. Contains 340384 sequences. (Running on oeis4.)