# Calculating permutations of a certain type

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!

• I would like to know your feedback on my answer – 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.

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}$
$$\frac{n!}{a_1!\cdot a_2!\cdots a_n!\cdot 1^{a_1}\cdot 2^{a_2}\cdots n^{a_n}}$$