Extraction of elements from a box I have a box with $n$ distinct elements and i need to do $n$ extractions with reposition. Let $N$ be the number of different elements that i found through the process I should try to find ${P}[N=k]$  for $k$ ranging between $1$ and $n$.
Here is my work. Let's take $\Omega$={$(x_{1},...,x_{n})\in R^{n}; x_{i}\in
{1,...,n}$}. I have that $\#\Omega$=$n^{n}$. 
Now I have problem calculating the cardinality of string with exactly $N$ elements. I need this as I would like to express my probability as a quotient of favorable cases over possible cases.
I guess that I should start with $\binom{n}{N}$ choosing the different collection of N elements that appear. Now i have to calculate how many different string of n elements I can get knowing that N and only N elements show up. I was trying with something such as counting surjective functions from $n\to N$. To so i tried do choose N elements from n, permutating them (it should show all the possible function) and letting the n-N elements range randomly. The problem is that my reasoning is wrong as i am clearly counting multiple times the same string, any help? Thanks.
 A: $$
\mathbb P(N=k)=\frac{\binom{n}{k}\cdot R(k,n)}{n^n}$$
where $$R(k,n)=k^n - (k - 1)^n \binom{k}{1} + (k - 2)^n \binom{k}{2} + \cdots + (-1)^j (k - j)^n \binom{k}{j} + \cdots + (-1)^{k - 1} \cdot 1^n
$$
is a number of ways to put $n$ distinct balls into $k$ distinct boxes in such a way that no empty boxes allowed. Look Proving a formula for distributing $n$ objects into $r$ non-empty boxes / formula for number of onto functions for $R(k,n)$.
A: Number the elements with $1,2,\dots,n$ and let $\hat{S}$ denote
the random set of elements that are found.
Then what we are after is: $$P\left(\left|\hat{S}\right|=k\right)$$
For a fixed $S\subseteq\left\{ 1,\dots,n\right\} $ we evidently have the equality:$$P\left(\hat{S}=S\right)=P\left(\hat{S}\subseteq S\right)-P\left(\bigcup_{s\in S}\left\{ \hat{S}\subseteq S-\left\{ s\right\} \right\} \right)$$
and applying inclusion/exclusion on term $P\left(\bigcup_{s\in S}\left\{ \hat{S}\subseteq S-\left\{ s\right\} \right\} \right)$
we arrive at: $$P\left(\hat{S}=S\right)=\sum_{T\subseteq S}P\left(\hat{S}\subseteq T\right)\left(-1\right)^{\left|S\right|-\left|T\right|}$$
For a fixed $T\subseteq S$ with cardinality $i$ we find: $$P\left(\hat{S}\subseteq T\right)=\left(\frac{i}{n}\right)^{n}$$
so if $S$ has cardinality $k$ then we can rewrite: $$P\left(\hat{S}=S\right)=\sum_{i=0}^{k}\binom{k}{i}\left(\frac{i}{n}\right)^{n}\left(-1\right)^{k-i}=n^{-n}\sum_{i=0}^{k}\binom{k}{i}i^{n}\left(-1\right)^{k-i}$$
The set $\left\{ 1,\dots,n\right\} $ has $\binom{n}{k}$ distinct
subsets that have cardinality $k$ so we finally arrive at: $$P\left(\left|\hat{S}\right|=k\right)=n^{-n}\binom{n}{k}\sum_{i=0}^{k}\binom{k}{i}i^{n}\left(-1\right)^{k-i}$$
