Count the number of permutations of certain cycles type

Question

Suppose we have $n$ elements, assume there is a permutations over $k$ elements among the $n$ elements so $n-k$ are fixed. Let that the permutation over the k elements is represented by permutation cycles so the length of all permutation cycles $=k$.

As an example: Suppose we have the following permutation

$$ x = \left( {\begin{array}{c} x_1 = \left( {\begin{array}{c} 1 \\ 2 \\ \end{array} } \right) \\ x_2 = \left( {\begin{array}{c} 3 \\ 4 \\ 5 \\ \end{array} } \right) \\ x_3 = \left( {\begin{array}{c} 6 \\ 7 \\ \end{array} } \right) \\ 8 \\ 9 \\ \vdots \\ 15 \\ \end{array} } \right)$$

My question: What is the number of permutations we can construct from the $n$ elements where each permutation should consists of the same cycles type?

Addition: I know that the number of $k-$cycles in the symmetric group $S_n$ is $\binom{n}{k}(k-1)!$ but I don't know what to do for the constraint asking that each permutation cycle has the same length in all permutations!

Answer 1

Hint: The number of distinct $k$-cycles is $P^n_k\cdot \dfrac 1k=\dfrac{n!}{(n-k)!}\cdot \dfrac 1k$.

To do your example, we would get, for permutations of type $(2,3,2)$ in $S_{15}$:

$P^{15}_2\cdot \dfrac 12\cdot P^{13}_3\cdot \dfrac 13\cdot P^{10}_2\cdot \dfrac 12=105\cdot572\cdot45=2702700$.

Now I need to divide by $2$, since I have double counted the two $2$-cycles.

So $\dfrac12\cdot2702700=1351350$.

See here, or here, for a good explanation.

Answer 2

Let's take your example of a cycle structure corresponding to the partition $3^1 + 2^2 + 1^8 \vdash 15$. I think the easiest way to handle the $a_i$ cycles of a given length $i$ is to select the lot (e.g. for the two two-cycles select four elements) and then repeatedly force the lower unselected element to be in the next $i$-cycle.

So we initially have 15 elements. We select three for the $3$-cycle in $\binom{15}{3}$ ways, leaving 12. Now we select four for the two $2$-cycles in $\binom{12}{4}$ ways, assign the lowest to one cycle along with one of the $\binom{3}{1}$ remaining ones; then assign the lowest to the next cycle along with the $\binom{1}{1}$ remaining one. Overall we get $$\left[\binom{15}{3} \binom{2}{2} \right] \left[ \binom{12}{4} \binom{3}{1} \binom{1}{1} \right] \left[ \binom{8}{8} \binom{7}{0} \binom{6}{0} \binom{5}{0} \binom{4}{0} \binom{3}{0} \binom{2}{0} \binom{1}{0} \binom{0}{0}\right]$$

In general, if we have $k$ items remaining to assign and $a_i$ cycles of length $i$ the term is $$\binom{k}{a_i i} \prod_{j=0}^{a_i - 1} \binom{(a_i - j) i - 1}{i - 1}$$