Number of ways you can form pairs with a group of people when certain people cannot be paired with each other.

Let's say you have a group of eight people and you want to form them into pairs for group projects.

There are $\frac{8!}{4! 2^4}$ ways to do it. ($8!$ is the total number of ways $8$ people can be arranged in a line. Divide that by $2^4$, which is the total number of ways the two people in each pair can be arranged. Then divide that by $4!$, which is the total number of ways those pairs can be arranged, and you have the number of possible ways a group of $8$ can be formed into pairs.)

Now, I want to take the same group of people and put them in different pairs for a second group project. How do I find the number of ways $8$ people can be formed into pairs with the constraint that they cannot work with the same person they worked with last group project?

Solution 1:

Given $n$ people, where $n$ is even, you can choose the first pair of people ${n \choose 2}$ ways, where ${n \choose 2}=\frac{n!}{2!(n-2)!}$. The next pair can be chosen in ${n-2\choose 2}$ ways, etc... The end result will be $\frac{n}{2}$ pairs which can be arranged in $\left(\frac{n}{2}\right)!$ ways. So there are $$\frac{{n \choose 2}{n-2 \choose 2}\dots{2 \choose 2}}{\left(\frac{n}{2}\right)!}=\frac{n!}{\left(\frac{n}{2}\right)!\,2^{\left(\frac{n}{2}\right)}}$$ ways to arrange all $n$ people into sets of pairs.

So for 8 people there are $\frac{8!}{4!\,2^{4}}=105$ possible sets of pairs.

Now the question remains, how many sets are there that do not contain any pairs from the original set?

Let $$f(x)=\frac{x!}{\left(\frac{x}{2}\right)!\,2^{\frac{x}{2}}}$$

If $S=\left\{p_{1}, p_{2}, ..., p_{\frac{n}{2}}\right\}$ is our original set of pairs and $P_{k}$ is the set of all sets containing $p_{k}$, where $1\le k\le\frac{n}{2}$ then by the inclusion-exclusion principal the number of sets not containing any of the original pair is:

$$f(n)-\left(|P_{1}|+|P_{2}|+\dots+|P_{\frac{n}{2}}|\right)+\left(|P_{1}\cap P_{2}|+(|P_{1}\cap P_{3}|+\dots\right)-\dots$$

But for any $P_{k}$; $|P_{k}|=f(n-2)$ therefore, $|P_{1}|=|P_{2}|=\dots=|P_{\frac{n}{2}}|$and in general, given any $k$ where $1\le k\le \frac{n}{2}$, then $|P_{1}\cap P_{2}\cap\dots\cap P_{k}|=f(n-2k)-\dots$

So the number of sets not containing any of the original pair is:

$$f(n)-\left(f(n-2)+f(n-2)+\dots\right)+\left(f(n-4)+f(n-4)+\dots\right)-\dots$$

which equals:

$$f(n)-{\frac{n}{2}\choose 1}f(n-2)+{\frac{n}{2}\choose 2}f(n-4)-\dots$$

So in the case where $n=8$

$$f(8)-4f(6)+6f(4)-4f(2)+1f(0)=105-60+18-4+1=60$$

Solution 2:

There is a mistake in the accepted answer, the correct answer is 60.

In response to Richard Stanley's answer, he is counting the total number of ways you can choose the first matching and the second matching, rather than the number of ways to choose the second matching, given that the first matching is already determined. By symmetry, we can simply divide this by the total number of matchings to obtain the answer to the original question.

As other posters pointed out, this number is $(2n)! \over 2^n(n!)$ if there are $2n$ students. In the example with 8 students, this number is 105. Dividing 6300 (Stanley's answer for 8 students) by 105, we get that the answer to the question originally asked is 60.

Solution 3:

If $f(n)$ is the number of ways that $2n$ people can satisfy the conditions of the question, then it can be shown that $$ \sum_{n\geq 0}f(n)\frac{x^n}{(2n)!} = \frac{e^{-x/2}}{\sqrt{1-x}}. $$ This gives $f(2)=6$, $f(3)=120$, $f(4)=6300$, $f(5)=514080$, $f(6)=62785800$, etc. This is sequence A054479 on OEIS.