1
$\begingroup$

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.

$\endgroup$
10
  • $\begingroup$ There is only one way to note have ET and Bob on the team, that it, not keeping both of them on the team. There are three ways to not have ET or Bob on the team, which you have described. $\endgroup$ Apr 9 '19 at 18:42
  • $\begingroup$ Okay, then you have drawn the cases correctly. Now you must ask yourself whether your cases are mutually exclusive to be able to simply add the case-wise ways to get the total ways. $\endgroup$ Apr 9 '19 at 18:44
  • $\begingroup$ I don't think they are mutually exclusive. How do I account for this? $\endgroup$
    – user641672
    Apr 9 '19 at 18:45
  • $\begingroup$ Note here that 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. $\endgroup$ Apr 9 '19 at 18:46
  • $\begingroup$ 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})$$ $\endgroup$ Apr 9 '19 at 18:48
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Ok I think I get it. But doesn't "no bob $\cup$ no ET" mean "neither bob nor ET can be on the team?" I want "not both Bob and ET can be on the team" $\endgroup$
    – user641672
    Apr 9 '19 at 19:01
  • $\begingroup$ Also how can we have ${n_1 - 1 \choose k_1}$ when we might have $k_1 = n_1$? Then it wouldn't work $\endgroup$
    – user641672
    Apr 9 '19 at 19:03
  • $\begingroup$ $\cup$ means union, the set-theoretic equivalent of the logical $OR$ operator. $\cap$ means intersection, which is equivalent to $AND$. $\endgroup$ Apr 9 '19 at 19:03
  • $\begingroup$ When $n_1=k_1,n_1-1<k_1$, so $\binom{n_1-1}{k_1}=0$, meaning that we can't have a team without ET, which is true seeing as how we need exactly $k_1=n_1$ aliens in the team. $\endgroup$ Apr 9 '19 at 19:04
  • $\begingroup$ @effunna9 English can be frustrating at times. The phrase "Neither..nor" is in fact equivalent to "Not..and also not". Letting $P$ and $Q$ be logical statements, you have "Neither $P$ nor $Q$" is equivalent to $(\neg P)\wedge (\neg Q)$ which is further equivalent to $\neg (P\vee Q)$. Compare to "Not $P$ or not $Q$" which is $(\neg P)\vee (\neg Q)$ which is equivalent to $\neg (P\wedge Q)$ which unlike the earlier phrase will be true in the case of exactly one of $P,Q$ being true with the other false. $\endgroup$
    – JMoravitz
    Apr 9 '19 at 23:18
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy