Choosing a team without two people

Question

If there are $n_{1}$ aliens and $n_{2}$ humans and we want to put $k_{1}$ aliens and $k_{2}$ humans on a team, there are ${n_1\choose k_1} \cdot {n_2 \choose k_2}$ ways to do this.

What if we do not want ET, an alien, and Bob, a person, to be on the team? Then how many teams can be made? There are three cases (two ways in which we can have one on, other off and one way in which we can have both off). So there are ${n_1 - 1\choose k_1- 1}{n_2\choose k_2} + {n_1\choose k_1}{n_2 - 1\choose k_2-1} + {n_1 - 1\choose k_1 - 1}{n_2 - 1\choose k_2 - 1}$ ways.

Are these correct? I'm less certain about the second reasoning.

Answer 1

No, this is wrong. The cases where Bob and ET are both not on the team are included in all three counts.

Hint: Inclusion-exclusion principle

Answer 2

When you exclude Bob from the team, you have no restriction on ET. You are counting the teams which may or may not have ET. Thus, you have already counted the teams in which neither Bob nor ET appear.

Similarly, when you exclude ET, you may or may not have Bob. So you have already accounted for the case in which none of them are in the team.

From set theory,$$n(A\cup B)=n(A)+n(B)-n(A\cap B)\\n(\text{no Bob }\cup\text{ no ET})=n(\text{no Bob})+n(\text{no ET})-n(\text{no Bob }\cap\text{ no ET})$$

We can select a team without Bob in $n(\text{no Bob})=\binom{n_1}{k_1}\cdot\binom{n_2-1}{k_2}$ ways. We can select a team without ET in $n(\text{no ET})=\binom{n_1-1}{k_1}\cdot\binom{n_2}{k_2}$ ways. We can select a team without both Bob and ET in $n(\text{no Bob }\cap\text{ no ET})=\binom{n_1-1}{k_1}\cdot\binom{n_2-1}{k_2}$ ways.

The required answer is $\binom{n_1}{k_1}\cdot\binom{n_2-1}{k_2}+\binom{n_1-1}{k_1}\cdot\binom{n_2}{k_2}-\binom{n_1-1}{k_1}\cdot\binom{n_2-1}{k_2}$.

Answer 3

You want to count the cases where the team can contain Bob or ET (or neither), but not both. This can indeed be counted as the $3$ separate (i.e. disjoint) cases. There is no need to use inclusion-exclusion.

• Bob, no ET: The "no ET" part contributes ${n_1 - 1 \choose k_1}$, because you are choosing $k_1$ from among the $n_1 - 1$ non-ET aliens. The "Bob" part contributes ${n_2 - 1 \choose k_2 - 1}$, because you are choosing the rest of the human teammates ($k_2 -1$ of them) from the $n_2 - 1$ non-Bob humans. Total $={n_1 - 1 \choose k_1}{n_2 - 1 \choose k_2 - 1}$

• ET, no Bob: By similar logic: ${n_1 - 1 \choose k_1 - 1}{n_2 - 1 \choose k_2}$

• no ET, no Bob: By similar logic: ${n_1 - 1 \choose k_1}{n_2 - 1 \choose k_2}$

These $3$ cases are disjoint, so you can just add them up:

$${n_1 - 1 \choose k_1}{n_2 - 1 \choose k_2 - 1} + {n_1 - 1 \choose k_1 - 1}{n_2 - 1 \choose k_2} + {n_1 - 1 \choose k_1}{n_2 - 1 \choose k_2}$$

In other words, you had the right idea (counting $3$ disjoint cases) but the $3$ terms in your summation were wrong.

Note that while my method counted the $3$ disjoint cases, it arrives as the same answer as @ShubhamJohri using inclusion-exclusion. The two answers look different but they are in fact the same, which can be easily proven using the identity ${a \choose b} = {a-1 \choose b} + {a-1 \choose b-1}$