number of ways to obtain a given permutation from k swaps

459 Views Asked by At

Let $\sigma_1, \ldots, \sigma_b \in S_n$ be all the 2-cycles ("swaps") in $S_n$. (So, $b = \binom{n}{2}$.) Given some $\pi \in S_n$, is there a known formula for how many ways to obtain $\pi$ as a product of $k$ swaps? (This can of course be zero when $k$ is too small.) It is easy to see that the answer only depends on the conjugacy class of $\pi$. Thus, I'm wondering whether there is some nice formula in terms of $k$, $n$, and the sizes of the cycles in the cycle-decomposition of $\pi$.