Random Matching in a Group Recently I was asked such a question: N people joined a party. In this party, there is a present exchange game where each one prepares a present, these presents will be randomly shuffled and re-distributed. If there are two people receive presents prepared by the other, they become a pair of "lovers"(Regardless of sex, and one can be his own "lover"). What is the probability of generating at least one pair of lovers in this party? E.g. If there are two people in this party, the probability would be 1; and for three people, it would be 1-2/6 = 2/3.
 A: The number of ways not to have a pair of lovers is the number of permutations of the $n$ presents that don't have 2-cycles. Using the symbolic method (see for example Flajolet and Sedgewick's "Analytic Combinatorics"), this class is described by the (hacky) symbolic equation for labelled classes:
$$
\mathcal{C} = \mathop{MSet}(\mathop{Cyc}(\mathcal{Z}) - {\mathop{Cyc}}_{= 2}(\mathcal{Z}))
$$
The respective exponential generating function is:
$$
\begin{align*}
C(z) &= \exp \left(- \ln (1 - z) - \frac{z^2}{2} \right) \\
     &= \frac{\exp \left(- \frac{z^2}{2} \right)}{1 - z}
\end{align*}
$$
Dividing by $1 - z$ gives partial sums, so what we are looking at is:
$$
c_n = n! \left. \exp \right|_{\lfloor n / 2 \rfloor} ( - 1 / 2 )
$$
Here $\left. \exp \right|_k (z)$ is the truncated exponential function, i.e., go only up to $k$-term in the exponential's series. The requested value is $n! - c_n \approx n! (1 - e^{-1/2})$, some 40% of parties have at least a pair of lovers.
This explains @ByronSchmuland's mystery, by the way.
A: It looks like you want the probability that there is a cycle of length 1 or 2 in a random permutation on $\{1,\dots,N\}$. Considering the complementary event, we'd need to count the number of permutations without such small cycles. These values can be found here (including the party of size $N=1$), which give us the following probabilities for $1\leq N\leq 10$:
$$1, 1, {2\over 3}, {3\over 4}, {4\over 5}, {7\over 9}, {65\over 84}, {373\over 480}, {1259\over 1620}, {2447\over 3150}$$ or
$$1., 1., .66667, .75000, .80000, .77778, .77381, .77708, .77716, .77683$$
These converge pretty rapidly to $1-\exp(-1.5)=.77686984$, but at the moment I'm not sure why.

Added: The number $C_1$ of one cycles is approximately Poisson(1), while the number  $C_2$ of two cycles is approximately Poisson(1/2). Also, they are asymptotically independent so $C_1+C_2$ is  approximately Poisson(3/2), and hence $\mathbb{P}(C_1+C_2=0)\approx \exp(-3/2)$.
Reference: Example 10.5.2 $\ $ Short cycles in random permutations from the book "Poisson Approximation" by A.D. Barbour, Lars Holst, and Svante Janson. The authors show that the number of cycles less than or equal $f$, is approximately a Poisson random variable with mean $\sum_{r=1}^f 1/r$, and also give bounds on the error.
