# Count the number of permutations of certain cycles type

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!

• So in short you want to count elements of $S_n$ with a given cycle structure? – Peter Taylor May 10 at 12:20
• @PeterTaylor Whatever was the cycle structure, it should be the same in all permutations! – Noah16 May 10 at 12:23

## 2 Answers

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.

• Thanks for your cooperation. I know this formula and I wrote it in the question previously because I thought it could be useful but unfortunately I don't know how to use it! – Noah16 May 10 at 13:06
• For instance, there are $P^6_2\cdot\dfrac 12=15$ two-cycles in $S_6$ . – Chris Custer May 10 at 16:29
• Thanks a lot. So a general formula will always consists of (divided by) a term represents the number of counts for cycles of the same size! – Noah16 May 13 at 8:51
• . My approach essentially leads to the same result as in the links (after adjusting for double counting. ) – Chris Custer May 13 at 9:34
• Yes I got it but I think you should divide it by 4 not 2 ? – Noah16 May 14 at 10:15

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}$$

• Thanks for you answer but really I didn't understand your last formula! how you didn't use or benefit from the total number of elements (n)? – Noah16 May 10 at 12:57
• I tried previously to benefit from the formula given in this answer math.stackexchange.com/questions/2127069/… Unfortunately I didn't achieve a solution – Noah16 May 10 at 13:00
• The last expression is for a term of the product which makes the full solution, which are marked with $[]$ in the example. $k$ will be $n$ for the first term of the product. – Peter Taylor May 10 at 15:09