Counting permutation cycle types

51 Views Asked by At

I have a permutation matrix $\sigma_\alpha$, corresponding to a permutation $\alpha \in S_n$, from which I construct the larger permutation matrix

$\sigma_2 = \left[\begin{array}{cc} 1& \mathbf{0}^T \\ \mathbf{0} &\sigma_\alpha \end{array}\right]$.

This (to me) describes a circular permutation (as per Wolfram's definition) but just fixing the position of the first element on the ring. Now further defining the shift matrix

$ \sigma_+ = \left[\begin{array}{cccccc} 0& 0& \ldots& 0 & 0 & 1\\ 1& 0& \ldots& 0 & 0 & 0\\ 0& 1& \ldots& 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots &\vdots & \vdots\\ 0 & 0 & \ldots&1 & 0 & 0 \\ 0 & 0 & \ldots& 0 & 1 & 0 \end{array}\right]$

I form the commutator

$\sigma = \sigma_+^{-1} \sigma_2^{-1} \sigma_+ \sigma_2$.

which is a $n+1$-permutation ($\sigma \in S_{n+1}$) albeit, since $\sigma$ can only take $n!$ different values (corresponding to the $n!$ different $\alpha$), this does not completely span $S_{n+1}$.

My problem is that I'd like to count how many times the different cycle structures/type (i.e. the number of cycles of different lengths) of $\sigma$ occur across all different possible permutations $\alpha$.

From the definition of $\sigma$ I can see that it must be an even permutation which I thought might be enough to define the set defined by $\sigma$, however, this didn't go far since the alternating group $A_{n+1}$ which has $(n+1)!/2$ elements which is too many. I also thought about whether I could expand the set of $\sigma$, to correspond to $A_{n+1}$ through cyclic permutations (and then worry about how to work backwards later) but the permutations I got when I did this for some test $n$ did not seem to correspond. I'm not really sure how to approach this problem, if its even possible.