Timeline for How many symmetric strings a permutation fixes
Current License: CC BY-SA 3.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 4, 2018 at 16:36 | comment | added | thedude | @Jan-ChristophSchlage-Puchta I have asked a related question here, mathoverflow.net/questions/292081/…, perhaps you might have a look | |
| Feb 4, 2018 at 16:35 | comment | added | thedude | @darijgrinberg I have asked a related question here, mathoverflow.net/questions/292081/…, perhaps you might have a look | |
| Oct 25, 2017 at 17:06 | comment | added | thedude | Right, but you do seem willing to provide more details | |
| Oct 25, 2017 at 16:58 | comment | added | Jan-Christoph Schlage-Puchta | Uhm, my answer is not different from Darij grinberg's answer. | |
| Oct 25, 2017 at 16:48 | comment | added | Jan-Christoph Schlage-Puchta | Hence the number of such $\pi$ is bounded by $\sum_\ell\binom{n}{\ell}(2n-2\ell)!(2\ell)! = (2n)!\sum_\ell\binom{n}{\ell}\binom{2n}{2\ell}^{-1}$. Comparing the sum to a geometric series we get that this expression is $(2n)!(\frac{2}{n}+\mathcal{O}(n^{-2})$. | |
| Oct 25, 2017 at 16:46 | comment | added | thedude | @Jan-ChristophSchlage-Puchta Might I suggest you write an answer? | |
| Oct 25, 2017 at 16:43 | comment | added | Jan-Christoph Schlage-Puchta | @WhatsUp: Almost all means that as $n\rightarrow\infty$, the proportion of $\pi\in S_{2n}$ having this property tends to 1. To see this note first that for an orbit of size $\ell$ there are $(2n-\ell)!\ell!$ permutation leaving this orbit invariant. If $\sigma$ is the involution mapping $k$ to $2n-k+1$, then the number of $\pi\in S_{2n}$, such that $\langle\pi, \sigma\rangle$ is not transitive, is at most $\sum_{A\subseteq [2n]} (2n-|A|)!|A|!$, where $\sum_A$ runs over all sets satisfying $k\in A\Rightarrow 2n-k+1\in A$. The number of such sets of size $2\ell$ is $\binom{n}{\ell}$. | |
| Oct 25, 2017 at 13:13 | comment | added | WhatsUp | @Jan-ChristophSchlage-Puchta And what does "almost all" mean in this context? | |
| Oct 25, 2017 at 9:34 | comment | added | Jan-Christoph Schlage-Puchta | Equivalently the answer is $N^c$, where $c$ is the number of orbits of the group generated by $\pi$ and the involution mapping $k$ to $2n+1-k$. In this formulation it is clear that for almost all $\pi$ the answer is $N$. | |
| Oct 25, 2017 at 3:13 | comment | added | darij grinberg | The answer should be $N^c$, where $c$ is the number of equivalence classes on the set $\left\{1,2,\ldots,2n\right\}$ with respect to the equivalence relation which relates each $k$ both with $\pi\left(k\right)$ and with $2n+1-k$. | |
| Oct 25, 2017 at 0:38 | review | Close votes | |||
| Oct 25, 2017 at 10:03 | |||||
| Oct 24, 2017 at 23:36 | comment | added | thedude | Oh, sorry! I was going to post this in MSE, ended up posting it in MO by mistake! Apologies... | |
| Oct 24, 2017 at 22:57 | history | asked | thedude | CC BY-SA 3.0 |