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!

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

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.

  • $\begingroup$ 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! $\endgroup$ – Noah16 May 10 at 13:06
  • $\begingroup$ For instance, there are $P^6_2\cdot\dfrac 12=15$ two-cycles in $S_6$ . $\endgroup$ – Chris Custer May 10 at 16:29
  • $\begingroup$ 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! $\endgroup$ – Noah16 May 13 at 8:51
  • $\begingroup$ . My approach essentially leads to the same result as in the links (after adjusting for double counting. ) $\endgroup$ – Chris Custer May 13 at 9:34
  • $\begingroup$ Yes I got it but I think you should divide it by 4 not 2 ? $\endgroup$ – 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}$$

  • $\begingroup$ 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)? $\endgroup$ – Noah16 May 10 at 12:57
  • $\begingroup$ I tried previously to benefit from the formula given in this answer math.stackexchange.com/questions/2127069/… Unfortunately I didn't achieve a solution $\endgroup$ – Noah16 May 10 at 13:00
  • $\begingroup$ 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. $\endgroup$ – Peter Taylor May 10 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.