- #1
GwtBc
- 74
- 6
- Homework Statement
- A little girl is painting on a blank paper. She has N colors available to her. Each time she selects one of these colors with replacement to draw with. Each trial is independent.
(There are some ensuing questions but eventually the following problem is posed:)
Suppose there are n=N trials and ##E_i## is the event that the color i is not used. By using the inclusion-exclusion principle on ##\cup_{1 \leq i \leq N}E_i## prove the following identity:
$$ N! = \sum_{k=0}^{N} (-1)^k \binom{N}{k} (N-k)^N$$
- Relevant Equations
- Inclusion-exclusion principle is given by:
$$Pr(A_1 \cup A_2 ... \cup A_n) = \sum Pr(A_i) - \sum_{i<j} Pr(A_i \cap A_j) + ... + (-1)^{n-1} Pr(A_1 \cap A_2 ... \cap A_n) $$
Well ##\cup_{i} E_i## is just the event that at least one color is not used, so its probability is given by ##1- (1/N)^N##. Now if I is a subset of {1,...,N} where ##\left | I \right | = l## then ##Pr(\cap_{i\in I} E_i) = (1-l/N)^N## (I'm guessing this is where I'm making a mistake?). So then we will have for example that
$$ \sum_{1\leq i < j < s < m \leq N} Pr(E_i\cap E_j \cap E_s \cap E_m) = \binom{N}{4} (1-4/N)^N$$
But when I plug these values into the inclusion exclusion for ##\cup E_i##, I get the required expression but with 1 on the LHS instead of ##N!##. It's possible to prove the identity using induction, but that's not the question and also not getting this out means there's something wrong with the probabilities I'm using which is worrying.
Thanks in advance for the help.
$$ \sum_{1\leq i < j < s < m \leq N} Pr(E_i\cap E_j \cap E_s \cap E_m) = \binom{N}{4} (1-4/N)^N$$
But when I plug these values into the inclusion exclusion for ##\cup E_i##, I get the required expression but with 1 on the LHS instead of ##N!##. It's possible to prove the identity using induction, but that's not the question and also not getting this out means there's something wrong with the probabilities I'm using which is worrying.
Thanks in advance for the help.