[Math] Creating two groups where two people can’t be in the same group.

combinatorics

If you have a group of $12$ men and $10$ women, and you need to make two groups – one with $6$ people and the other with $9$, the ways to form such groups would be

$${22 \choose 6}\cdot {16 \choose 9}$$

Since I guess the order doesn't matter.

But then, there is another constraint: Bob (male) and Hilda (female) cannot be in the same group.

For the time being, maybe I can remove them from the whole thing, and make one group with $5$ people and another with $8$ without them:

$${20 \choose 5}\cdot {15 \choose 8}$$

There are now $7$ people left, plus Bob and Hilda we got $9$. There is one spot free in the first group and another one in the second.

If Hilda is placed in the first group, then it is guaranteed Bob won't be in it (because it's full), so he would end up in the second group and viceversa.

So I guess the answer would be like this?

$${20 \choose 5}\cdot {15 \choose 8} \cdot 9 \cdot 8$$

Best Answer

The way I was taught to do it - is to generalise. We forget 12,10, 6,9 and all.

We think that we have total n people, who should be divided into a and b so :-

$ n = a + b$ And then there is a pair who can not be put into a group. Well well. Then what we do is to forcefully make them into a group. Let the count where they are forced to sit in a group is $N_{in}$. And total all possible count is $N_{all}$. Clearly then :- $$ N_{all} = N_{in} + N_{OUT} $$ where $N_{OUT}$ is the count that they are not in the same group! Now let's solve it. To find $N_{in}$ we need to consider the pair together as same entity, that reduces the total from n to $n - 1$. But I am sure we already know how to shuffle $n-1$ into two groups. Note the size too should be reduced from a to $a-1$. So, we will get $N_{in}$. Same way, we can get $N_{all}$ without any constraints. And then taking minus - we are done.

Related Question