|
| |
|
|
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
|
|
|
|
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
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
|
|
|
|
KEYWORD
|
nonn,more,hard
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
