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).
No, your answer is not correct.
The goal is to count the number of permutations $p\in S_{2n}$ such that in the disjoint cycle representation of $p$, the maximum cycle length is $n$.
You need to worry about the case where $p$ is a product of two disjoint $n$-cycles.
Thus, consider two cases . . .
Case $(1)$:$\;$The disjoint cycle representation of $p$ has only one cycle of length $n$.
For case $(1)$, the count is
$$\binom{2n}{n}{\,\cdot\,}(n-1)!{\,\cdot\,}\bigl(n!-(n-1)!\bigr)$$
Explanation:
- The factor ${\large{\binom{2n}{n}}}$ counts the $n$-element subsets of $\{1,...,2n\}$ used to form the $n$-cycle.$\\[4pt]$
- The factor $(n-1)!$ counts the cyclic orderings of the $n$ elements used for the $n$-cycle.$\\[4pt]$
- The factor $n!-(n-1)!$ counts the $n!$ permutations of the remaining $n$ elements, but excludes the $(n-1)!$ permutations that would form an $n$-cycle.
Case $(2)$:$\;p$ is a product of two disjoint $n$-cycles.
For case $(2)$, the count is
$$\binom{2n}{n}{\,\cdot\,}\bigl((n-1)!\bigr)^2{\,\cdot\,}\bigl({\small{\frac{1}{2}}}\bigr)$$
Explanation:
- The factor ${\large{\binom{2n}{n}}}$ counts the $n$-element subsets of $\{1,...,2n\}$ used to form the first $n$-cycle.$\\[4pt]$
- The factor $\bigl((n-1)!\bigr)^2$ counts the cyclic orderings of the elements for the two $n$-cycles.$\\[4pt]$
- The factor ${\large{\frac{1}{2}}}$ corrects for the double-count, since we can freely switch the order of the two $n$-cycles, without affecting the result.
Summing the counts for the two cases, and then simplifying, we get a total count of
$$
(2n-1)!{\;\cdot}\left(\frac{2n-1}{n}\right)
$$
Best Answer
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.