1

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!

Noah16
  • 247

2 Answers2

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.

  • 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 '19 at 13:06
  • For instance, there are $P^6_2\cdot\dfrac 12=15$ two-cycles in $S_6$ . –  May 10 '19 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 '19 at 08:51
  • . My approach essentially leads to the same result as in the links (after adjusting for double counting. ) –  May 13 '19 at 09:34
  • Yes I got it but I think you should divide it by 4 not 2 ? – Noah16 May 14 '19 at 10:15
  • I think it's by two; and it agrees with the other formulas (linked). –  May 14 '19 at 16:06
-1

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

Peter Taylor
  • 13,425
  • 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 '19 at 12:57
  • I tried previously to benefit from the formula given in this answer https://math.stackexchange.com/questions/2127069/number-of-permutations-with-given-cycle-types Unfortunately I didn't achieve a solution – Noah16 May 10 '19 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 '19 at 15:09