|
|
A186752
|
|
Length of minimum representation of the permutation [n,n-1,...,1] as the product of transpositions (1,2) and left and right rotations (1,2,...,n).
|
|
2
|
|
|
0, 1, 2, 4, 8, 13, 19, 26, 34, 43, 53
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
COMMENTS
|
Example: Taking "0" to indicate the "left" rotation (1,2,...,n) -> (2,3,...,n,1), "1" to represent the transposition (1,2), and "2" to indicate the "right" rotation (1,2,...,n) -> (n,1,2,...n-1), the sequence 10010121 (length = 8) is a minimal sequence producing the reverse permutation on S_5.
It was suggested that a(10) = 61, but this cannot be correct. It would conflict with A186783(10)=45, the diameter of the set under these same operations. We must have a(n) <= A186783(n) for all n. - Tony Bartoletti, Mar 08 2019
|
|
LINKS
|
|
|
PROG
|
(Sage) def A186752(n): t = tuple(1..n); G = PermutationGroup([[(1, 2)], [t], PermutationGroupElement([t])^(-1)]); t=list(t); t.reverse(); return G.cayley_graph().distance(G([()]), G(t)) # Max Alekseyev, Sep 09 2011
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,more,hard
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|