Finding the number of combinations of secret santa pairs I am currently attempting to calculate the number of potential unique combinations of unique pairs of a set of Secret Santa participants. This topic was discussed at length last year and nobody knew how to go about working it out - this year I want to be prepared!
What I have so far is that I can derive the number of possible unique pairs by subtracting 1 from the number of participants n, which I then multiply by the number of participants n, and finally divide by 2:
$\frac{n\times(n-1)}{2}$
Here's an example:
$\frac{6\times(6-1)}{2} = 15$
What I now need to find out is how many potential combinations of those pairs are possible...
...so if there are 4 participants in Secret Santa:
[A, B, C, D]
Using my formula above, there would be 6 unique pairs:
[A,B],[A,C],[A,D],[B,C],[B,D],[C,D]
I know that the possible unique combinations of those pairs are:

[[A,B],[C,D]],
[[A,C],[B,D]],
[[A,D],[B,C]]
But I cannot figure out how to calculate this mathematically. Also, to add a spanner in the works, I would like to be able to calculate this whilst taking couples into consideration. So, if [A,B] are not a couple, then no unique pair or combination of pairs should include them. I obviously would just subtract the number of couples from the number of unique pairs, but for combinations I haven't got the foggiest.
Please forgive me if I am going about all this the wrong way, or haven't provided the right information. Also, can any answers given please include a working example? - thanks!
 A: You do not want to pair the peolpe up, they will all know who they are paired with and that will defeat the "secret" of who their Santa is.
What you need is a permutation of the set of people with no fixed points, these are known as derrangements, in combinatorial parlance. Your example with $4$ people will have $9$ possibilities. See here for more info about derrangements https://en.wikipedia.org/wiki/Derangement .
To calculate the number of derrangements the recurrence relation is $d_n=(n-1)(d_{n-1}+d_{n-2})$ and the first few values are $1,0,1,2,9,44,265,\cdots $
A: Suppose we have $2n$ persons $a_1,a_2,\dots,a_{2n}$.
Notice each permutation of the persons gives us a pairing by pairing up the first two persons, the next two persons and so on.
For example, the permutation $a_1,a_4,a_2,a_3,a_6,a_5$ gives us the pairs $[a_1,a_4],[a_2,a_3],[a_6,a_5]$.
Every possible paring can be obtained in this way in exactly $2^n n!$ ways. (because there are $n!$ ways to order the pairs and $2^n$ ways to order the two persons within the pairs).
The answer is thus $\frac{(2n)!}{n!2^n}$
