4
$\begingroup$

Let $\mathbb{S}_m$ be the symmetric group on $m$ letters. Let $n=m-1$. Let $\mathbf{w}=a_1\cdots a_r$ be a word on the alphabet $\{1,\ldots,n\}$. We say that $\mathbf{w}$ gives rise to an enumeration of elements of the symmetric group $\mathbb{S}_m$ if $1,s_{a_r},s_{a_{r-1}}s_{a_r},\ldots,s_{a_2}\cdots s_{a_r},s_{a_1}\cdots s_{a_r}$ are all distinct elements of the symmetric group $\mathbb{S}_m$.

For example, $32323132323132323$ gives rise to an enumeration of elements of the symmetric group $\mathbb{S}_4$, and I think it is (one of) the longest possible such words.

Q. What is the length $r(n)$ of the longest word which gives rise to an enumeration of elements of the symmetric group $\mathbb{S}_m$. Is it always possible to find such a word of length $m!$, or only for $\mathbb{S}_3$?

$\endgroup$
6
  • 6
    $\begingroup$ You are trying to list all $m!$ permutations in $\mathbb{S}_m$ in such a way that each permutation in the list is obtained from the previous one by interchanging two adjacent entries. This is done in Knuth's TAoCP, volume 4A, Section 7.2.1.2, under the subheading "Adjacent interchanges". (This is one of the things classically referred to as "change ringing".) $\endgroup$ Commented Aug 11, 2020 at 9:13
  • 1
    $\begingroup$ An old version of Section 7.2.1.2 is available at www-cs-faculty.stanford.edu/~knuth/fasc2b.ps.gz . $\endgroup$ Commented Aug 11, 2020 at 9:15
  • 4
    $\begingroup$ Based on your questions list, you might like Conway's "Gray Codes for Reflection Groups" which generalizes this to all finite reflection groups. $\endgroup$ Commented Aug 11, 2020 at 13:12
  • 1
    $\begingroup$ Is $s_a$ the transposition $(a, a + 1)$? $\endgroup$
    – LSpice
    Commented Aug 11, 2020 at 14:18
  • 1
    $\begingroup$ @LSpice Yes, it is the simple transposition. $\endgroup$ Commented Aug 12, 2020 at 5:15

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.