Given the set of n elements: $\mathbb{A} = \{1,…,n\}$.
Fix $k$ elements in the set. And consider a random permutation $\pi : \mathbb{A} \rightarrow \mathbb{A}$.
So any permutation can be represented by the product of cycles.
How to determine the probability that all k fixed elements of the set $\mathbb{A}$ are in one cycle.
My result is :
$$ \frac{\sum_{i = 0}^{n – k} {{k+i} \brack {1}} \binom{n-k-i+1}{i}(n – k – i)!}{n!} $$
where ${a \brack b}$ – a Stirling number of the first kind
Best Answer
Start with some element $a$ of the $k$ elements and then in each step map the current element to an element selected uniformly at random from the elements not yet selected. The probability that all $k$ elements are in the same cycle is the probability that this process selects $a$ as the last of $k$ elements. Since all $k$ elements are equally likely to be selected last, the probability is $\frac1k$.
Edit: Since you seem to also be interested in a proof that sums over the cycle lengths, here's how I originally arrived at the $\frac1k$ result: There can be $m$ additional elements in the cycle together with the $k$ elements, with $0\le m\le n-k$. There are $(m+k-1)!$ different cycles containing the $m+k$ elements, and $(n-m-k)!$ different ways to permute the remaining elements. Thus the desired probability is
\begin{align} \frac1{n!}\sum_{m=0}^{n-k}\binom{n-k}m(m+k-1)!(n-m-k)! &=\sum_{m=0}^{n-k}\frac{(n-k)!(m+k-1)!}{n!m!}\\ &=\frac1k\frac1{\binom nk}\sum_{m=0}^{n-k}\binom{m+k-1}m\\ &=\frac1k\;, \end{align}
where the last step uses the Christmas stocking theorem (also known as the hockey stick identity).