Simple but long permutation and combination problem

Question

Question: There are 115 people in a room, they are divided into 3 groups, A, B, C with 37, 41, and 37 people in each respectively. You have to conduct 5 vs 5 matches in the room and a team MUST have atleast one person from each group. Find number of matchups possible. Exact answer preferred. Each person is unique and one person can not be on both teams.

Answer 1

Blithely disregarding the request for an exact answer, here is a rough approximation.

First, if we disregard the groups, in how many ways can we form two teams of $5$ members each from the $115$ people in the room? The answer is a multinomial coefficient, $$\binom{115}{5 \; 5 \;95} = \frac{115!}{5! \;5! \;95!}$$ This assumes the teams are distinguished, for example the Blue team and the Red team. If they are not distinguished, we have counted each pair of teams twice and we would need to divide by $2$.

If we form a team of $5$ members at random, what is the probability that it will include at least one member from each of the three groups? This is not terribly different from the Coupon Collector's Problem where there are three types of coupons and we have collected five coupons. The answer to the Coupon Collector's Problem is that the probability that we will have a complete set of three types among our five coupons is $0.617284$ (see below). Here we have disregarded the fact that the groups are slightly different sizes, so the probabilities of selection are a bit different from $1/3$, and also that the members are sampled without replacement. Still, it seems a useful approximation.

If the probability that one team will have at least one person from each group is $0.617284$, then the probability that both teams will have at least one person from each group should be about $(0.617284)^2$. This assumes that one team's chance of having a complete set is independent of the other team's chance of also having a complete set. This is false, but probably not too far wrong.

So it seems the number of ways to form two teams of five with each team including at least one person from each of the three groups should be about $$ \binom{115}{5 \; 5 \;95} \times (0.617284)^2 \approx 2.77 \times 10^{15}$$

---

The Coupon Collector's Problem: If there are $n$ types of coupons and we have collected $N$ coupons, then the probability that we have a complete set of types is $$1- \sum_{i=1}^{N-1} \binom{N}{i} \left( \frac{N-i}{N} \right)^n (-1)^{i+1}$$ Reference: Ross, A First Course in Probability, Seventh Edition, Section 4.1, Example 1e. For $n=3$ and $N=5$, this formula yields $0.617284$.

Answer 2

There are ${4\choose2}=6$ admissible ways to compose a team of $5$ from the three groups A, B, C, namely $$(3,1,1),(1,3,1),(1,1,3),(2,2,1),(2,1,2),(1,2,2)\ .\tag{1}$$ In setting up two teams $P$ and $Q$ we first have to choose independently two partitions $p$ and $q$ from the list $(1)$. Then we have to select the actual people in the three groups A, B, C according to the multiplicities prescribed by $p$ and $q$. As an example take $p:=(1,3,1)$, $q:=(2,2,1)$. We then can choose the $5+5$ people in $${37\choose 1}{41\choose3}{37\choose1}\ \cdot\ {37-1\choose2}{41-3\choose2}{37-1\choose1}$$ ways. There are $6\cdot6=36$ computations of this kind to be performed. Summing the results up and dividing by $2$ gives $$N=3\,735\,293\,958\,155\,520\approx 3.7\cdot 10^{15}\ .$$