2
$\begingroup$

Let $g$ be an element of the permutation group $S_n$ and let $\eta$ be the cyclic permutation $(1,2,\dots,n)$. Define $D(g)$ as the number of cycles in permutation $g$.

I am aware of the fact that the maximum of $D(g) + D(\eta^{-1} \circ g)$ is $n+1$, corresponding to the non-crossing partitions, $NC_n$. I am further aware of the fact that the number of such partitions with $D(g) = k$ is given by the Narayana number $N(n,k)$. I would like to understand further the structure of these permutations.

More precisely, define the set of $g$'s such that $g \in NC_n$ and $D(g) =k$ as $X_{n,k}$. For $h \in X_{n,k}$, we define $(m^{(h)}_1, m^{(h)}_2, \dots, m^{(h)}_n)$ as a list where $m^{(h)}_i$ is the number of cycles in $h$ of length $i$. We must have $\sum_i m^{(h)}_i = k$. How many elements of $X_{n,k}$ have $(m^{(h)}_1, m^{(h)}_2, \dots, m^{(h)}_n)$ and $(\tilde{m}^{(\eta^{-1}\circ h)}_1, \tilde{m}^{(\eta^{-1}\circ h)}_2, \dots, \tilde{m}^{(\eta^{-1}\circ h)}_n)$ where $m$'s and $\tilde{m}$'s are, in general, different. (Note that $\sum_i \tilde{m}_i^{(\eta^{-1}\circ h)} = n +1-k$).

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ If you just want the number of permutations $g$ with $m_i$ $i$-cycles such that $\eta^{-1}g$ has the maximum number of cycles, then you are enumerating noncrossing partitions with $m_i$ $i$-element blocks. This was done by Kreweras. The number is $n(n-1)\cdots(n-k+2)/m_1!m_2!\cdots m_n!$, where $k=\sum m_i$ (the total number of blocks). See e.g. equation (3) of core.ac.uk/download/pdf/82503989.pdf. $\endgroup$
    – Richard Stanley
    Dec 6, 2020 at 16:54
  • $\begingroup$ @Richard Stanley, thank you very much for your comment. I am actually interested in something more. You gave the number of permutations $𝑔$ with $π‘š_𝑖$ such that $πœ‚^{βˆ’1}𝑔$ has the maximum number of cycles. I would like to know how many of these permutations $𝑔$ with $π‘š_𝑖$ have $πœ‚^{βˆ’1}𝑔$ with $\tilde{m}_𝑖$? $\endgroup$
    – combinatorix_curious
    Dec 12, 2020 at 20:15
  • $\begingroup$ I don't know how to do this more refined problem. $\endgroup$
    – Richard Stanley
    Dec 14, 2020 at 0:58

0

Reset to default

Your Answer

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