http://openproblemgarden.org/op/shuffle_exchange_conjecture Comments for "Shuffle-Exchange Conjecture" en http://openproblemgarden.org/op/shuffle_exchange_conjecture <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/bene_vaclav_e">Beneš</a>; <a href="/category/folklore">Folklore</a>; <a href="/category/stone_harold_s">Stone</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/combinatorics">Combinatorics</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <p>Given integers <img class="teximage" src="/files/tex/1041e1f578aec49a27fbc841578eac3503c9f753.png" alt="$ k,n\ge2 $" />, let <img class="teximage" src="/files/tex/858410106f855d4731af6a7f19dd3ded70f81b08.png" alt="$ d(k,n) $" /> be the smallest integer <img class="teximage" src="/files/tex/5f847fb92dc3a28dd4495bb65e05d91f5c09f74b.png" alt="$ d\ge2 $" /> such that the symmetric group <img class="teximage" src="/files/tex/173f5240e010842148ef6aee5e393aafae82f7a5.png" alt="$ \frak S $" /> on the set of all words of length <img class="teximage" src="/files/tex/ec63d7020a64c039d5f6703b8fa3ab7393358b5b.png" alt="$ n $" /> over a <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" />-letter alphabet can be generated as <img class="teximage" src="/files/tex/b4aab129bf3c2a86d97d972d87f8ff6006e32cd6.png" alt="$ \frak S = (\sigma \frak G)^d:=\sigma\frak G \sigma\frak G \dots \sigma\frak G $" /> (<img class="teximage" src="/files/tex/aeba4a4076fc495e8b5df04d874f2911a838883a.png" alt="$ d $" /> times), where <img class="teximage" src="/files/tex/aa48c7f2c6265dba4f1ddd17f840b1faa62683db.png" alt="$ \sigma\in \frak S $" /> is the <em>shuffle permutation</em> defined by <img class="teximage" src="/files/tex/7be772211e6563d47c513ef63e015b0a4c813be1.png" alt="$ \sigma(x_1 x_2 \dots x_{n}) = x_2 \dots x_{n} x_1 $" />, and <img class="teximage" src="/files/tex/e34f89bfa75da8a360b1741f9a1718bbdfcc8927.png" alt="$ \frak G $" /> is the <em>exchange group</em> consisting of all permutations in <img class="teximage" src="/files/tex/173f5240e010842148ef6aee5e393aafae82f7a5.png" alt="$ \frak S $" /> preserving the first <img class="teximage" src="/files/tex/da6174078cbeae6601684c08526200d9254caa11.png" alt="$ n-1 $" /> letters in the words. </p> <div class="envtheorem"><b>Problem&nbsp;&nbsp;(SE)</b>&nbsp;&nbsp; Evaluate <img class="teximage" src="/files/tex/858410106f855d4731af6a7f19dd3ded70f81b08.png" alt="$ d(k,n) $" />. </div> <div class="envtheorem"><b>Conjecture&nbsp;&nbsp;(SE)</b>&nbsp;&nbsp; <img class="teximage" src="/files/tex/b83b000fc1d6dd29fb829a03beffef104b4df30e.png" alt="$ d(k,n)=2n-1 $" />, for all <img class="teximage" src="/files/tex/1041e1f578aec49a27fbc841578eac3503c9f753.png" alt="$ k,n\ge2 $" />. </div> </tr></td> </table> </td> </tr> </table> Beneš, Václav E. Folklore Stone, Harold S. Combinatorics http://openproblemgarden.org/op/shuffle_exchange_conjecture#comment Fri, 27 Nov 2009 22:06:34 +0100 Vadim Lioubimov 37167 at http://openproblemgarden.org