Prove expression for N using inclusion-exclusion principle

[GwtBc]

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.

 

[timetraveller123]

you might have to use combinatoric arguments
the $N!$ on lhs represents that all the N colours need to be placed in the N trial hence N!
now you need to inclusion exclusion principle to obtain the right hand side ie find the number of ways it is possible to colour using every colour. so in this context it is
$\binom N 0 N^N - |E_1 \cup E_2 \cup ... \cup E_N|$
and since if you use every colour it has to equal N! the two expression are equivalent( i think , i might be wrong)

 

[GwtBc]

I think I figured out my error which was that $Pr(\cup_i E_i) = 1- (1/N)^N$. This probability is in fact equal to $1 - N!/N^N$ since there are N! orders of picking all the different colors. Now the expression comes out nicely.

I do believe this was @timetraveller123 's idea as well.