6
$\begingroup$

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?

$\endgroup$

migrated from mathoverflow.net Apr 14 '15 at 18:25

This question came from our site for professional mathematicians.

  • $\begingroup$ The general problem is hard; this specific problem not so much. Since there are 105 ways (you missed a factor of 8), you can almost by hand enumerate the other possibilities. One observation you can make is that there will be two pairs in the first group which will not meet in the second grouping. This should help you compute the total number for the second grouping. Also, this is the wrong forum for your question. Gerhard "Ask Me About Simply Grouping" Paseman, 2015.04.14 $\endgroup$ – Gerhard Paseman Apr 14 '15 at 17:47
  • 2
    $\begingroup$ The formula should be $\frac{8!}{4!(2!)^4}$; you need to divide by the number of ways of rearranging each of the four pairs among themselves. $\endgroup$ – Dustan Levenstein Apr 14 '15 at 17:50
8
$\begingroup$

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$$

$\endgroup$
  • $\begingroup$ Thank you! It took me a couple of days to understand some of your notation, but once I did, it was exactly the answer I was looking for! $\endgroup$ – Tara Roys Apr 16 '15 at 19:36
  • $\begingroup$ Glad I could help! Sorry if the notation was not always clear. I struggled to find the right balance. Too far in the 'plain English' direction and you lose the precision and accuracy of mathematical notation. Things become open to interpretation. Too much mathematical notation and it can become terse and and unapproachable. The answer could become incomprehensible to the people that may benefit most from it. $\endgroup$ – Jason Boyd Apr 17 '15 at 0:27
  • $\begingroup$ As an aside, edits do not offend me. If somebody can improve the answer feel free. $\endgroup$ – Jason Boyd Apr 17 '15 at 0:45
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for pointing that out Sam. There was an error in the final calculation. I had $6f(4)=36$ which resulted in the final answer of $78$. The correct calculation is $6f(4)=18$ which gives the correct result of $60$. Thanks again. $\endgroup$ – Jason Boyd Apr 22 '15 at 12:18
  • $\begingroup$ Actually, could you elaborate more with regards to comments on Richard Stanley's answer? It is not clear to me what he is doing. $\endgroup$ – Jason Boyd Apr 22 '15 at 12:39
  • $\begingroup$ Is your question about what he is counting (which I already tried to clarify), or how is is counting it? $\endgroup$ – Sam Clearman Apr 22 '15 at 13:17
  • $\begingroup$ How. I am not even sure what $x$ represents in his summation or the final equation. If $n$ is the number of people (or pairs of people) what is $x$? If $x>1$ you end up with an imaginary number in the denominator. $\endgroup$ – Jason Boyd Apr 22 '15 at 13:42
  • $\begingroup$ $x$ is a formal variable, it doesn't represent anything. See en.wikipedia.org/wiki/Generating_function $\endgroup$ – Sam Clearman Apr 22 '15 at 13:44
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ why isn't it $e^{x/2}+1$, since the coefficiants of $x^n$ are $\frac{1}{n!2^n}$, differentiating yields the sum $S$ without the initial term, however it is divided by two. So $\frac{S-1}{2}=\frac{dS}{dx}$? $\endgroup$ – Dis-integrating Dec 27 '16 at 11:04
0
$\begingroup$

I believe that your argument above is incorrect. Think about having 4 people: you can pair them in 3 different ways, but 3 is different from 4!/(2!*2!). I believe that the number of pairings without restrictions is 8!/(4!*2^4), that is num_people!/(num_pairs!*2^num_pairs).

For the number of possible pairings so that everybody is with someone else, you can compute the total number of pairings and then subtract the number of possible pairings where someone is working with the same person as in the previous project, using the inclusion/exclusion principle.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.