Calculate probability that both $1$ and $2$ will be in the same cycle

Question

I solved this task and but I am not sure about my solution, can somebody check that?

Let consider random space of random n-permutation for $2\le n$; Elementary events are $n-$permutations and each of them has the same probability $\frac{1}{n!}$. Calculate probability that both $1$ and $2$ will be in the same cycle.

$$P(\mathbb A) = \frac{\sum_{k}^{n-2} \binom{n-2}{k}\cdot (k+1)! \cdot (n-2-k)!}{n!}$$ We choose $k$ elements to complete our cycle, permutate them (with accuracy to shift) , and other elements just permutate. It gives me result $$ \frac{n}{2(n-2)} $$

Answer 1

Your first formula looks good (assuming the sum starts from $k=0$), but the simplification is not correct, and for $n=3$ gives a "probability" of $1.5$.

Your formula actually simplifies to $$\frac{\sum_{k=0}^{n-2}(n-2)!(k+1)}{n!}=\frac{\sum_{k=0}^{n-2}(k+1)}{n(n-1)},$$ which then gives $1/2$.

There is an easier way to see this. Choose $f(1)$ at random, then $f(f(1))$ (randomly from numbers not chosen so far), and so on, until you either hit $1$ or $2$. If you hit $2$ before $1$ then they will be in the same cycle, otherwise they are in different cycles. But $1$ and $2$ are equally likely to be chosen at every step.

Answer 2

Another elegant solution is to use the well-known transition lemma, which states that the following map is a bijection from the set of all n-permutations to itself:

Write a permutation $\sigma$ in its standard form, i.e., in cycle form with the smallest element in each cycle written first and with cycles sorted in decreasing order by their first element. For example, $\sigma = (3576)(2)(14)$ is in standard form. Remove the parenthesis to obtain $f(\sigma)$. In this case, we have $f(\sigma) = 3576214$.

It is indeed not difficult to prove that $f$ is a bijection. Note that in a random $\sigma$ of length $n$, there is equal chance for $1$ to be before $2$ or vice versa. The two elements are in the same cycle in in $f^{-1}(\sigma)$ if and only if $1$ is before $2$ in $f^{-1}(\sigma)$.