Probability that 1,2,3 and 4,5 lie in a seperate cycle of a permutation from 1 to 100 You are given a random permutation from $\{1, \dots, 100\}$
e.g: $ \pi \in S_{100}$
What is the probability of the event E = [1,2,3 lie in the same cycle and 4,5 lie in a distinct one]
The correct solution is:  P(E) = 1/60
My try:
I don't even know where to start..
 A: Let's do it by induction on the size of permutation. I will denote the size as $n$. Moreover, in my argument, 
$A_n = \left\{ \sigma \in S_n : \sigma \textrm{ satisfies the conditions} \right\}$
 $a_n$ means the number of permutations in $S_n$ satisfying conditions and $p_n = \frac{a_n}{n!}$.
At the first, we will start at $n=5$. 
The number $a_5$ of permutations in $S_5$ satisfying the conditions is 2, the total number of $S_5$ is 120. So the probability $p_5$ is $\frac{1}{60}$.
Let assume that we know the number $a_n$. My claim is that $a_{n+1} = (n+1)a_n$
For each $\sigma \in A_n$, we can classify the number 1 to n into 3 categories. 
The category A means the numbers which are in the same cycle with 1,2,3. The category B means the numbers which are in the same cycle with 4,5. The category C consists of the numbers which are not in the categories A and B. 
Let $T$ be the set of all numbers in category A. Then we can give an order on the set $T$ by following ways. 
$$T = \left\{t_1 = 1, t_2 = \sigma(1), \cdots, t_{\alpha} =\sigma^{\alpha-1}(1)  \right\}$$
where $\alpha =$ size of $T$. In other word, the category A corresponding $\sigma$ can be represented as $t_1 t_2 \cdots t_{\alpha}$
By the same way, the category B has a representation $r_1 r_2 \cdots r_{\beta}$.  
Let $S$ be the set of numbers in category C, and let 
$$ S = \left\{ s_1 < s_2 < s_3 < \cdots <  s_{\gamma} \right\} $$
Then the cycle has unique representation $\sigma(s_1) \sigma(s_2) \cdots \sigma(s_{\gamma})$
For each $\sigma \in A_{n+1}$, by removing $n+1$, we get unique $\sigma' \in A_n$. Conversely, by adding $n+1$ for each $\sigma' \in A_n$, we can count the number of $A_{n+1}$.
Let assume that $n+1$ is added to the category A. Then we can add $n+1$ in the representation $t_1 t_2 \cdots t_{\alpha}$ and get another representation $t'_1 t'_2 \cdots t'_{\alpha+1}$of A added $n+1$. But we know that $t'_1 =1$, so there are $\alpha$ ways to add $n+1$ in the category A.
By the same reason, there are $\beta$ ways to add $n+1$ in the category B.
For the category C, there is no conditions about adding $n+1$. So there is $\gamma+1$ ways to add $n+1$ in the category C.
So for each $\sigma \in A_n$, there are $\alpha + \beta + \gamma + 1 = n+1$ ways to add $n+1$. ($\alpha$, $\beta$, $\gamma$ are the sizes of categories A,B,C respectively, so $\alpha + \beta + \gamma = n$)
This means that $a_{n+1} = (n+1)a_n$.
By the definition, $$p_n=\frac{a_n}{n!}=\frac{(n+1)a_n}{(n+1)n!}=\frac{a_{n+1}}{(n+1)!}=p_{n+1}$$
By induction on $n$, $p_n = \frac{1}{60}$ for all $n$
A: This is easiest using something called the canonical cycle representation of permutations. This involves taking a rearrangement of the list $1,\dots,n$, for example,
$$
6\,10\,3\,2\,7\,9\,8\,1\,5\,4
$$
Then placing a $"("$ before it, a $")"$ after it, and a $")("$ before every left-to-right minima, meaning an element which is smaller than everything to its left. In this case,we get
$$
(6\,10)(3)(2\,7\,9\,8)(1\,5\,4)
$$
This is then interpreted in cycle form. Every permutation can be represented uniquely in this way (by decomposing it into cycles, making sure the cycles have their lowest element first, ordering the cycles in decreasing order of their first element, then dropping the parentheses). 
Some thought shows that given a random permutation in canonical cycle form, your conditions will be met exactly the 4 comes before the 5 comes before the 1, and the 2 and 3 are after the 1. Since each of the $5!$ possible relative orderings of the elements 1,2,3,4,5 is equally likely, and only 2 of those orderings (4,5,1,2,3 and 4,5,1,3,2) meet your criteria, the probability of success is $\frac2{5!}=\frac1{60}$.
I wasn't able to find a lot of references for the canonical cycle representation, but it is useful in proving a number of surprising results about random permutations and cycles. Here's another example.
A: The first answer can be streamlined. Note that $n=5$ is the smallest to admit a solution, which is a combination of one of two three-cycles and one possible two-cycle giving probability $2/120 = 1/60.$ Now consider the disjoint cycle representation of a permutation. A permutation on $n+1$ elements is obtained from one on $n$ elements either by placing $n+1$ somewhere on the existing cycles ($n$ possibilities) or adding it as a fixed point, so the total count goes up by a factor of $n+1.$ Exactly the same goes for our admissible permutations with $1,2$ and $3$ on one cycle and $4$ and $5$ on another, again giving a factor of $n+1.$ Therefore the ratio never changes and the probability always stays at $1/60.$
