cp's OEIS Frontend

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

%I A186783 #79 Jun 24 2025 00:59:45
%S A186783 0,1,2,6,10,15,21,28,36,45,55,66,78
%N 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).
%C A186783 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.
%C A186783 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.
%C A186783 Conjecture from Chervov et. al., section 4.2: The longest and unique element of S_n is (1,2)(n,3)(n-1,4)(n-2,5)... = (2,1,n,n-1,n-2,...,3). The conjecture holds for n <= 13. - _Dmitry Kamenetsky_, Jun 22 2025
%H A186783 Danilo Bazzanella, Antonio Di Scala, Simone Dutto, and Nadir Murru, <a href="https://arxiv.org/abs/2002.08062">Primality tests, linear recurrent sequences and the Pell equation</a>, arXiv:2002.08062 [math.NT], 2020.
%H A186783 A. Chervov, A. Soibelman, S. Lytkin, et al., <a href="https://arxiv.org/abs/2502.18663">CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs</a>, arXiv:2502.18663 [cs.LG], 2025. See pp. 1, 2, 4, 18, 24.
%H A186783 Sai Satwik Kuppili and Bhadrachalam Chitturi, <a href="https://arxiv.org/abs/2002.07342">An Upper Bound for Sorting R_n with LRE</a>, arXiv:2002.07342 [cs.DS], 2020.
%F A186783 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
%F A186783 Conjecture: a(n) = n*(n-1)/2 for all n>3. - _Per W. Alexandersson_, Aug 25 2020
%F A186783 Conjectures from _Colin Barker_, Aug 26 2020: (Start)
%F A186783 G.f.: x^2*(1 - x + 3*x^2 - 3*x^3 + x^4) / (1 - x)^3.
%F A186783 a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3).
%F A186783 (End)
%e A186783 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.
%t A186783 a[1] = 0; a[n_] := GraphDiameter[CayleyGraph[PermutationGroup[{Cycles[{{1, 2}}], Cycles[{Range[n]}], InversePermutation[Cycles[{Range[n]}]]}]]]; (* _Ben Whitmore_, Jan 09 2018 *)
%o A186783 (Sage) def a(n): return PermutationGroup([[(1, 2)], [tuple(1..n)], PermutationGroupElement([tuple(1..n)])^(-1)]).cayley_graph().diameter() # _Max Alekseyev_, Sep 09 2011
%Y A186783 Cf. A039745, A186752, A000217.
%K A186783 nonn,more,hard
%O A186783 1,3
%A A186783 _Tony Bartoletti_, Feb 26 2011
%E A186783 a(8)=28 added by _Tony Bartoletti_, Mar 12 2011
%E A186783 a(9)=36 added by _R. H. Hardin_, Sep 09 2011
%E A186783 a(10)=45 added by _Sharon Li_, Mar 09 2013
%E A186783 a(11)=55 and a(12)=66 added by _James Bieron_, Mar 15 2013
%E A186783 a(13)=78 added by _Ben Whitmore_, Jan 09 2018