I've some troubles calculating the total numbers of permutations of a specific type:

"How many permutations in $\ S_{10}$ are of type (3,5) and how many of type (4,4)?"

For the type, I assume permutations $\omega_i \in \ S_{10}$ of type (3,5) are made by one 3-cycle, one 5-cycle and two 1-cycle, something like: $\omega_1$ = (1 2 3)(4 5 6 7 8)(9)(10) = (1 2 3)(4 5 6 7 8).

Same for permutations $\sigma_i \in \ S_{10}$ of type (4,4) : something like $\sigma_1$ = (1 2 3 4)(5 6 7 8)(9)(10) = (1 2 3 4)(5 6 7 8)

I'm not sure if I'm correctly interpretating the definition of type of a permutation.

Latest, for the total number of permutations, I'm calculating in this way:

  • Permutations $\omega_i \in \ S_{10}$ of type (3,5) : $\frac{10!}{3 * 5 * 1^2}$
  • Permutations $\sigma_i \in \ S_{10}$ of type (4,4) : $\frac{10!}{4^2 * 1^2 * 2!}$ , where 2! is added because we have two 4-cycles.

If I should calculate the number of permutations $\delta_i\in \ S_{50}$ of type (2,5,5,6,6,6,10,10) with the same technique: $\frac{50!}{2 * 5^2 * 6^3 * 10^2 * 2! * 3! * 2!}$ where 2!*3!*2! are the exponents, which are the "repeated" cycles of the same length.

Is this the correct way? Thanks you!

  • $\begingroup$ I would like to know your feedback on my answer $\endgroup$ – G Cab Jul 18 '17 at 15:10

Concerning "interpretation", well that's a standard way to classify permutations, based on their cycle structure, so yours is a plausible interpretation.

We can represent a given permutation through its cycles, as in one of your example $$ \left( {1,2,3} \right)\left( {4,5,6,7,8} \right)\left( 9 \right)\left( {10} \right) $$ However, that same permutation cold be represented as well by $$ \left( {4,5,6,7,8} \right)\left( {3,1,2} \right)\left( 9 \right)\left( {10} \right) $$ that is, the cycles can be permuted between them, and each cycle can be internally cyclically permuted.

The representation can be made univocal if
- each cycle is taken to start with its (e.g.) lowest element;
- the cycles are ordered (e.g. increasingly) according to their first element;
which is the example you gave.

Another univocal representation is possible, and is more convenient for the calculations you are requiring, which is:
- each cycle is taken to start with its (e.g.) lowest element;
- the cycles are ordered firstly by their length and secondly by their first element; in this way our example becomes $$ \left( 9 \right)\left( {10} \right)\left( {1,2,3} \right)\left( {4,5,6,7,8} \right) $$

Permutations can be partitioned according to what is called the cycle structure, which corresponds to a vector $C$ where each component $C_k$ represents the number of cycles of length $k$, and clearly $$ \sum\limits_{1\, \le \,k\, \le \,n} {k\,C_{\,k} } = n $$ with $n$ being the number of elements of the permutation.
Our example will correspond to $$ C = \left( {2,0,1,0,1,0,0,0,0,0} \right) $$

So, as interpreted, the problem is asking the number of permutations corresponding to a given cycle structure $C$.

The number of ways to compose a $k$-cycle from $m$ available elements is the same as that of composing a $k$-subset from a $m$-set, multiplied by the $(k-1)!$ number of ways to permute the elements beyond the first, which is assumed to be the lowest. So $$ N_{\,k} (m) = \left( {k - 1} \right)!\left( \matrix{ m \cr m - k \cr} \right) = \left[ {k \le m} \right]{{m!} \over {k\,\left( {m - k} \right)!}} $$ where $[P]$ denotes the Iverson bracket.

To compose $C_k$ $k$-cycles from $m$ available elements, the number of ways will be $$ \eqalign{ & N_{\,k} (m)N_{\,k} (m - k)\, \cdots \,N_{\,k} (m - k\,C_{\,k} )/C_{\,k} ! = \cr & = \left[ {k\,C_{\,k} \le m} \right]{1 \over {k^{\,C_{\,k} } \,C_{\,k} !}}{{m!} \over {\,\left( {m - k\,C_{\,k} } \right)!}} \cr} $$ where the division by $C_k!$ is because the cycles order is fixed.

Thus the number of permutations of $n$ elements with a given cycle structure $C$ is: $$ N(C) = \;{{n!} \over {\prod\limits_{1\, \le \,k\, \le \,n} {k^{\,C_{\,k} } C_{\,k} !} }} = \;{{\left( {\sum\limits_k {k\,C_{\,k} } } \right)!} \over {\prod\limits_k {k^{\,C_{\,k} } C_{\,k} !} }} $$ refer for instance to this paper.

Thus your calculation is correct.

| cite | improve this answer | |
  • $\begingroup$ Due to an incoming math exams I completely forgot to mark your answers, It was clear and well explained, helped me a lot with the permutation chapter, thanks you! $\endgroup$ – Alessandro Aug 27 '17 at 17:18
  • $\begingroup$ @Alessandro glad that it was useful $\endgroup$ – G Cab Aug 27 '17 at 22:08

not it is not correct. for the first type: $\frac{10!}{(3! \cdot 5!\cdot 1^3\cdot 2^5}$, for the second type: $\frac{10!}{(4!)^2\cdot 1^4\cdot 2^4}$

in general:

$$\frac{n!}{a_1!\cdot a_2!\cdots a_n!\cdot 1^{a_1}\cdot 2^{a_2}\cdots n^{a_n}}$$

| cite | improve this answer | |

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.