Limit of probability that a permutation of $\mathcal{S}_n$ has a $k$-cycle is $1 - e^{-1/k}$? Choose a random permutation $\sigma \in \mathcal{S}_n$. What's the probability that it contains a $k$-cycle as you take $n \to \infty$?
I ran a couple examples and it seems to approach $1 - e^{-1/k}$. Can anyone explain this phenomenon?
 A: Permutations are counted by cycles using the exponential generating function
$$
\frac1{1-z}=\exp\log\frac1{1-z}=\exp\left(\sum_{j=0}^\infty\frac{z^j}j\right)\;,
$$
where the $j$-th term corresponds to $j$-cycles (see Wikipedia). To count the number of permutations without $k$-cycles, we can drop the $k$-th term to obtain
$$
n![z^n]\exp\left(\sum_{j=0}^\infty\frac{z^j}j-\frac{z^k}k\right)
=
\frac1{1-z}\exp\left(-\frac{z^k}k\right)\;,
$$
where $[z^n]$ denotes extraction of the coefficient of $z^n$. This coefficient is the sum of all coefficients up to $n$ in $\exp(-z^k/k)$. For $n\to\infty$, that becomes the sum of all coefficients, which is the value at $1$, i.e. $\mathrm e^{-1/k}$. Dividing by the number $n!$ of permutations in $S_n$ to obtain the probability for a random permutation not to contain a $k$-cycle cancels the factor $n!$, so the probability tends to $\mathrm e^{-1/k}$, and the complementary probability that a random permutation contains a $k$-cycle tends to $1-\mathrm e^{-1/k}$, in agreement with your results.
