Home » Basic probability » inclusion-exclusion formula
Category Archives: inclusion-exclusion formula
Taking classes
There are 18 students in a room. How many students are not majoring in math or science or computer science ?
7 of them are math majors
10 of them are science majors
10 of them are computer science majors
4 of them are math and cs majors
3 of them are science and math majors
5 of them are cs and science majors
1 of them is a math, cs and science major
Chewing gum
Baseball players are chewing gum. Given gum flavor counts determine how many players were sampled.
22 of them chew fruit flavored gum
25 of them chew spearmint flavored gum
39 of them chew grape flavored gum
9 of them chew fruit and spearmint
17 of them chew spearmint and grape
20 of them chew fruit and grape
6 of them chew all
4 of them chew none
Stuffing Envelopes
You write a stack of thank you cards for people who gave you presents for your birthday. You address all of the envelopes but before you can stuff them you are called away. A friend tying to help you see the stack of cards and stuffs them in the envelops. Unfortunately they did not realize that each card was personalized and just stick them in the envelops randomly. Assuming there were \(n\) cards and \(n\) envelops, let \(X_{n}\) be the number of cards in the correct envelope.
- Find \(\mathbf{E} (X_n)\).
- Show that the variance of \(X_n\) is the same as \(\mathbf{E} (X_n)\).
- Is there any common distribution which has the above statistics ?
- (**) Show that
\[ \lim_{n\rightarrow \infty} \mathbf{P}(X_n =m) = \frac{1}{e\, m!}\]
De Morgan’s Laws
Let \( A\), \(B\), and \(C_i\) be events.
- Show that \( (A \cup B )^c= A^c \cap B^c\).
- Show that \( (A \cap B)^c = A^c \cup B^c \).
- \[ \Big( \bigcup_{i=1}^n C_i \Big)^c = \bigcap_{i=1}^n C_i^c\]
- \[ \Big( \bigcap_{i=1}^n C_i \Big)^c = \bigcup_{i=1}^n C_i^c\]
- (**) Argue that the above previous two statements hold even when \(n=\infty\).
Is it True (Event Manipulation)?
Which of the following are identically true ? For those that are not, say when they are true.
- \(A \cup (B\cap C) = (A\cup B) \cap (A \cup C)\)
- \(A \cap (B\cap C)= (A \cap B) \cap C\)
- \( A \cup B) \cap C = A \cup (B\cup C) \)
- \( A \setminus (B\cap C) = (A\setminus B) \cup (A \setminus C)\)
[GS2, p.1 # 5]
The matching problem
There are \(n\) letters addressed to \(n\) eople at different addresses. The \(n\) addresses are typed on \(n\) envelopes. A disgruntled secretary shuffles the letters and puts them in the envelopes in random order, one letter per envelope.
- Find the probability that at least one letter is put in a correctly addressed envelope. [Hint: use the inclusion-exclusion formula.]
- What is the probability approximately, for large \(n\) ?
[ For example, the needed inclusion-exclusion formula is given in Problem 12, p. 31 in Pitman]
You will also need to know the number of elements in the set
\[ \{ (i_1,i_2,\cdots, i_k) : 1 \leq i_1 < i_2 < \cdots < i_k\leq n\} \]
which is discussed here.
