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

0, 1, 2, 4, 8, 13, 19, 26, 34, 43, 53, 64, 76, 89, 103, 118, 134, 151, 169, 188, 208, 229, 251, 274, 298, 323, 349, 376, 404, 433, 463, 494, 526, 559, 593, 628, 664, 701, 739, 778, 818, 859, 901, 944, 988, 1033, 1079, 1126, 1174, 1223, 1273, 1324, 1376, 1429

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

Conjecture: for n>=4, a(n)=A186783(n)-2. Conjecture holds for n<=13. - Dmitry Kamenetsky, Jun 15 2025

Links

Paolo Xausa, Table of n, a(n) for n = 1..10000

Grigorii Antiufeev, A Lower Bound for the Diameter of Cayley Graph of the Symmetric Group S_n Generated by (12), (12...n), (1n...2), arXiv:2601.08715 [math.CO], 2026.

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

Sai Satwik Kuppili, C++ program for generating the moves for a given n

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

Index entries for linear recurrences with constant coefficients, signature (3,-3,1).

Formula

a(n) = n*(n-1)/2 - 2 for all n>3. The formula follows as the special case i = 0 of Theorem 1 in arXiv:2601.08715, for the general distance dist(s r^{n-i}, e). - Grigorii Antiufeev, Apr 24 2026

From Stefano Spezia, Jun 17 2026: (Start)

G.f.: x^2*(1 - x + x^2 + x^3 - x^4)/(1 - x)^3.

E.g.f.: 2 + 2*x + x^2 + x^3/6 + exp(x)*(x^2 - 4)/2. (End)

Mathematica

A186752[n_] := If[n <= 3, n-1, n*(n-1)/2 - 2]; Array[A186752, 60] (* Paolo Xausa, Jun 16 2026 *)
(* Alternative: *)
LinearRecurrence[{3, -3, 1}, {0, 1, 2, 4, 8, 13}, 60] (* Paolo Xausa, Jun 16 2026 *)

Prog

(SageMath) def a186752(n): t = tuple(1..n); G = PermutationGroup([[(1, 2)], [t], PermutationGroupElement([t])^(-1)]); return G.cayley_graph().distance(G.one(), G(list(t)[::-1])) # Max Alekseyev, Sep 09 2011

Crossrefs

Cf. A378834 (number of ways), A048200 (LE reversal distance).

Sequence in context: A037380 A328005 A379793 * A360512 A030503 A245094

Adjacent sequences: A186749 A186750 A186751 * A186753 A186754 A186755

Keyword

nonn,easy,changed

Author

Tony Bartoletti, Feb 26 2011

Extensions

a(9) from Max Alekseyev, Sep 09 2011

Incorrect value for a(10) deleted by N. J. A. Sloane, Mar 09 2019

a(10) and a(11) added by Sai Satwik Kuppili and Bhadrachalam Chitturi, Mar 28 2019

a(12) and a(13) from Kevin Ryde, Dec 12 2024

More terms from Sean A. Irvine, Jun 15 2026

Status

approved