Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

25 people randomly form partners with each other. They sunder and do it again. What's the probability that exactly 8 people get the same partner the second time?

There are $\frac{25 \times 24}{2} = 300$ partnerships formed per round of pairing up... the answer is clearly also not $\binom{300}{4}$ since the partnerships could differ every time...

share|improve this question
    
If all 25 people are allowed to form pairs, there should be $\binom{25}{2} \cdot \binom{23}{2} \cdots \binom{3}{2}$ ways of doing it and of course 1 person remains single. –  Alex Oct 9 '12 at 8:50
add comment

2 Answers 2

up vote 2 down vote accepted

This gets pretty messy (though it’s always possible that I’ve simply overlooked a nicer approach).

Number the people $1$ through $25$. To form one set of partnerships you can first choose which of the $25$ will be unpartnered. Then repeatedly assign a partner to the lowest-numbered person remaining; this can be done in $$23\cdot21\cdot19\cdot\ldots\cdot1=\frac{24!}{24\cdot22\cdot\ldots\cdot2}=\frac{24!}{2^{12}12!}$$ ways, so there are $$25\cdot23\cdot21\cdot19\cdot\ldots\cdot1=\frac{25!}{2^{12}12!}=7,905,853,580,625$$ possible pairings.

There is no harm in assuming that the original pairing leaves $25$ unpartnered. Say that a pairing is good if it shares exactly $8$ couples with the original pairing. We’ll count the good pairings in two groups.

Consider first a good pairing that leaves $25$ unpartnered. There are $\binom{12}8$ ways to choose which $8$ couples it shares with $P$. The other $4$ couples must all be broken up. Say that the couples involved are $\{p_1,p_2\},\{p_3,p_4\},\{p_5,p_6\}$, and $\{p_7,p_8\}$. Now $p_1$ and $p_2$ can get new partners from the same original couple or from different original couples.

  • If they come from the same original couple, there are $3$ ways to choose that couple and then $2$ ways to make the new pairings, for a total of $6$ ways to form the new couples. The remaining two original couples can then reform in $2$ ways, so there are altogether $3\cdot2\cdot2=12$ such ways to break up the $4$ couples.
  • There are $6\cdot4$ ways for $p_1$ and $p_2$ to get new partners from different original couples. The remaining $4$ people consist of one original couple and two other people; the original couple has to be broken up, so these $4$ can be paired up in $2$ ways. Thus, there are $6\cdot4\cdot2=48$ such ways to break up the $4$ couples.

There are therefore $\binom{12}8(12+48)=60\binom{12}8=29,700$ good pairings with $25$ unpartnered.

Now consider a good pairing that leaves some $k\ne25$ unpartnered. We retain $8$ of the other $11$ couples. If $25$ ends up with $k$’s original partner, that leaves $3$ original couples to be broken up, say $\{p_1,p_2\},\{p_3,p_4\}$, and $\{p_5,p_6\}$. If $25$ ends up with someone else, it leaves $2$ original couples and two ‘strays’, say $\{p_1,p_2\},\{p_3,p_4\},p_5$, and $p_6$.

  • In the first case there are $24$ choices for $k$ and $\binom{11}8$ choices for the couples to be retained. Then $p_1$ and $p_2$ must get new partners from different original couples, which can happen in $4\cdot2$ ways, so there are $8\cdot24\cdot\binom{11}8$ good pairings of this type.
  • In the second case there are $24$ choices for $k$, $22$ choices for $25$’s partner, and again $\binom{11}8$ choices for the couples to be retained. Then either $p_5$ and $p_6$ are partnered, in which case there are just $2$ ways to repartner $p_1,p_2,p_3$, and $p_4$; or $p_5$ and $p_6$ are partnered with members of different original couples, which can be done in $4\cdot2=8$ ways and allows no further choice. There are therefore $10\cdot24\cdot22\cdot\binom{11}8$ good pairings of this type.

This gives us a total of $$228\cdot24\cdot\binom{11}8=902,880$$ good pairings with $25$ partnered, and a grand total of $932,580$ good pairings.

The probability of getting a good pairing is $$\frac{932,580}{7,905,853,580,625}\approx 1.1796\times 10^{-7}\;.$$

share|improve this answer
add comment

I'm curious, since 25 people is an odd number of people because partnerships must include more than two people or else one person must be left out. What do you mean by partnerships? You spoke of pairing, which implies two person groups, but that is impossible with 25 people.

I might be way off base here, but I think you asked your question incorrectly. I think maybe you mean 24 or 26 people, or some other even number of people.

Let's assume you meant some even number of people $2n$ such that there are a total of $n$ pairs of people formed.

Let us start by thinking in terms of permutations. Out of $2n$ people, they can be permuted in $(2n)!$ ways.

Group these $2n$ people from left to right in pairs of two. Within each of these groups the order does not matter, and so there are 2 permutations in each pairing that is equivalent to another permutation. We divide the $(2n)!$ permutations by $2^n$, thereby dividing each of the $n$ pairs by 2 and accounting for these equivalent permutations.

Thus, there are $\frac{(2n)!}{2^n}$ permutations of unique 2-person pairings. But now we divide by $n!$, since there are $n$ pairs and their order amongst one another doesn't matter. So there are $\frac{(2n)!}{(n! 2^n)}$ unique combinations of pairs of people made from $2n$ people.

With 24 people that is 316,234,143,225 possible combinations of pairs.

With 26 people that is 7,905,853,580,625 possible combinations of pairs.

(And with 25 people we get undefined values for the factorial, and with the Gamma function we get fractional quantities of combinations.)

As for answering your probability question, I'm sorry but it's a bit over my head. At least at the moment it seems that way. My contribution at least gets you started by counting combinations correctly.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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