Welcome to our community

Be a part of something great, join today!

Problem of the week #81 - October 14th, 2013

Status
Not open for further replies.
  • Thread starter
  • Admin
  • #1

Jameson

Administrator
Staff member
Jan 26, 2012
4,052
The inclusion-exclusion principle shows that for two events $P[A \cup B]=P[A]+P-P[A \cap B]$ and for three events $P[A \cup B \cup C] = P[A] + P + P[C] - P[A \cap B] - P[A \cap C] - P[B \cap C] + P[A \cap B \cap C]$.

Using these as a guideline what is $P[A \cup B \cup C \cup D]$? In general, how many terms will be in \(\displaystyle P\left[ \bigcup_{i=1}^{n} A_i \right]\)?
--------------------
Remember to read the POTW submission guidelines to find out how to submit your answers!
 
  • Thread starter
  • Admin
  • #2

Jameson

Administrator
Staff member
Jan 26, 2012
4,052
Congratulations to the following members for their correct solutions:

1) Ackbach

Solution (from Ackbach):
The guideline yields the pattern of having to subtract, then add, then subtract, so as not to count things more than once. Based on that, we have that
\begin{align*}
P(A \cup B \cup C \cup D)&=P(A)+P(B)+P(C)+P(D) \\
& \quad -P(A \cap B)-P(A \cap C)-P(A \cap D)-P(B \cap C)-P(B \cap D)-P(C \cap D) \\
& \quad +P(A \cap B \cap C)+P(A \cap B \cap D)+P(A \cap C \cap D)+P(B \cap C \cap D) \\
& \quad -P(A \cap B \cap C \cap D).
\end{align*}
The pattern here for the number of terms is that
$$P \left[ \bigcup_{j=1}^{n}A_{j} \right]$$
has $2^{n}-1$ terms. Technically, it has $2^{n}$ terms, one for each possible subset; but $P[ \varnothing]=0$, so it'll never contribute to the sum.

Alternate solution:
We can see that $P[A \cup B \cup C \cup D]$ has 4 terms, then 3, then 3 then 1 if you partition the terms into the amount of intersections. Written another way, it has \(\displaystyle \binom{4}{1}+\binom{4}{2}+\binom{4}{3}+\binom{4}{4}\) terms. If we generalize this we can see that the number of terms in \(\displaystyle P \left[ \bigcup_{i=1}^{n}A_{i} \right]\) is \(\displaystyle \sum_{i=1}^{n}\binom{n}{i}\).
 
Status
Not open for further replies.