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$?

Improve this question
$\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$
    – darij grinberg
    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$
    – darij grinberg
    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$
    – Hugh Denoncourt
    Aug 11, 2020 at 13:12
  • 1
    $\begingroup$ Is $s_a$ the transposition $(a, a + 1)$? $\endgroup$
    – LSpice
    Aug 11, 2020 at 14:18
  • 1
    $\begingroup$ @LSpice Yes, it is the simple transposition. $\endgroup$
    – Christoph
    Aug 12, 2020 at 5:15

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy