Probability of 2 n-permutations meeting in k places. I have been thinking about think problem, however, I still do not really know how to tackle it.
We have two permutations of $n$ elements. What is the probability that these two permutations meet in exactly $k$ places ($k\in\{0,...,n\}$)? [Meeting in $k$ places means that they have the same numbers in $k$ places.]
I would really appreciate if you give me some ideas. Thank you!
 A: Let $\sigma$ and $\tau$ be two independently chosen random permutations on $\{1,2,\ldots,n\}$ (assuming that the distribution is uniform).  The required probability is the probability that $\sigma^{-1}\circ\tau$ has exactly $k$ fixed points.  If $D_r$ is the $r$-th derangement number, then the answer is $$\frac{\binom{n}{k}\,D_{n-k}}{n!}=\frac{D_{n-k}}{k!\,(n-k)!}\approx \frac{1}{\text{e}\,k!}\,,$$ where $\text{e}$ is the natural base of logarithm.
A: HINT: There are $\binom{n}k$ ways to choose the set $S$ of $k$ numbers on which the two permutations agree. Let $d_{n-k}$ be the number of derangements of the remaining $n-k$ numbers; then there are $\binom{n}kd_{n-k}$ permutations that leave $S$ fixed and derange $[n]\setminus S$. Thus, there are $\binom{n}kd_{n-k}$ permutations $\pi$ that agree with $\pi_0=\langle 1,2,\ldots,n\rangle$ in exactly $k$ places. Finally, the pair $\langle\pi_0,\pi\rangle$ can be permuted in $n!$ ways to get all $n!\binom{n}kd_{n-k}$ ordered pairs of permutations that agree in exactly $k$ places. There are $n!^2$ ordered pairs of permutations altogether.
