# Simple but long permutation and combination problem

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.

• What have you tried? Note: I'm not sure the problem is clear. Are the divisions into $A,B,C$ set or is that part of the problem? Does a "matchup" take into account the group? (that is, if I swap some team member Bob from group $A$ to group $B$ but leave the team members unchanged, assuming the group rules are still satisfied, is that a different matchup?) – lulu Jul 9 '18 at 10:24
• Let us first see how many teams can be formed first. (Not useful, but a good warming up.) One has to pick $(a,b,c)$ players (tuple notation, just ignore the parentheses) from the teams $A,B,C$, where $(a,b,c)$ is in the list $(3,1,1)$, (1,3,1)$, (1,1,3)$; $(2,2,1)$, $(2,1,2)$, $(1,2,2)$. In each of the mentioned cases it is easy how many possibilities there are for a team Pleas show the effort to compute this number, best, solve it completely, this is fair, else you cannot profit from a solution for the problem posted by a potential helper. – dan_fulea Jul 9 '18 at 10:39
• Lulu, yes that is correct and counts as a matchup, – Arch Cloud Jul 9 '18 at 11:07
• I have tried to compute the problem by finding out total number of possible combinations and subtracting from the particular cases which do not meet the conditions and failed. The main problem in all my attempts is counting the matchups which are repeated and subtracting them, I just can’t seem to find the exact no of repeating matchups. – Arch Cloud Jul 9 '18 at 11:08

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}\ .$$

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