Distribution of number of unique elements I've been stuck on the following problem for a few days and would really appreciate some help. This isn't homework. The context of this problem is that $m$ and $n$ may be extremely large but there's no restriction on their relative difference.
Suppose $X_1, X_2, ..., X_n \sim \: iid \enspace \mathcal{Unif}\{1, 2, ..., m\}$.
Find the distribution of $S$, the number of unique elements in the resulting vector $\left(x_1, x_2, ..., x_n\right)$.
I don't really know how to approach this analytically so I did some simulations [10,000 reps per plot] and observed the following:

It's clear that $S \leq min(m, n)$. When $m \approx n$ then the distribution looks like a normal/binomial and it gets increasingly negatively skewed as $|m - n|$ grows until just about every single outcome $s$ is equal to $min(m, n)$.
I'd also like to be able to determine the distribution of $S$ for cases where the distribution of the $X_i$ is something other than uniform, but I hope that the answer to this problem will point me in the right direction for this more general case. 
Thanks for any help!
 A: My first answer was wrong (I dont understood the problem correctly on the firsts reads) so I come again with a second try :p
Any vector can be written as a list of multiplicities of it composition, something like $L=(c_1 1,c_2 2,c_3 3,...,c_n n)$, where $\{c_1\}_{\max}=\min(m,n)$ and in general $\{c_i\}_{\max}=\lfloor\frac{\min(m,n)}{i}\rfloor$. And it taxicab norm $||L||_1=n$.

IMPORTANT NOTE: just for clarity $c_1$ is the number of unique elements in the vector, if my interpretation is correct about 'uniqueness', I interpreted here unique elements as the elements in the vector with multiplicity 1. I read the answer of @awkward so I noticed that for 'unique' could be the interpretation of 'different' elements.)

The different amount of vectors for each composition L are all possible distinguishable permutations of its components, a first level of permutations $\rho_1$ that is $\rho_1(L)=\frac{n!}{c_1 1!\cdot c_2 2!\cdot c_3 3!\cdots c_n n!}$,i.e., the multinomial coefficient for the L composition (any value of $c_j=0$ will be omitted because define an empty product).
A second level of permutations (more exactly deletion of repeated permutations) is $\rho_2(L)=\frac{\rho_1(L)}{c_1!\cdot c_2!\cdot c_3!\cdots c_n!}=n!\prod_{j=1}^{n}\frac{c_j!c_j}{j!}$. This is a reduction of permutations over the groups of the same multiplicity. We did this because we can put any value from 1 to m on any groups so it will create repeated vectors cause groups with the same multiplicity.
The third and last level of permutations will be the different amount of variations of the m elements on $\sum c_j$, i.e.
$$\rho_3(L)=\rho_2(L)\cdot (m)_{\sum c_j}=(m)_{\sum c_j}n!\prod_{j=1}^{n}\frac{c_j!c_j}{j!}$$
You can do an algorithm that sequentially create all the L, by example, starting with $c_1=1$ and the rest all pairs. After pairs and triples, after pairs and triples and... Anyway it maybe hard to enumerate. And you can calculate the frequency of each one that is $\rho_3$.
The worst is that these L configurations are all the possible partitions (or with some restriction if $m<n$) of the number n but the cases with $c_1=0$.
The partition of a number isnt a easy task at all and the number of partitions increases very fast and is a HUGE number. You can search for information and you will notice.
So I think there isnt a clear "analytical" solution to this task... IMO it is way better to see how the distributions change using some simulation as you tried at first. May exist a way to make a continuous approximation with defined amount of error over the frequencies but Im not sure about this.
You can try to create a continuous approximation seeing what happen when you increases $c_1$ over a batch of experiments with not too high m and n.
Well Idk if this information maybe helpful or just too sad :S
If my approach is useful (what Im not sure because after all Im not mathematician and my knowledge is limited) I found two interesting articles[1][2] about the distribution of addends of the partition of a number (with a lot of interesting bibliography over the topic and related topics).
A: this is only scratching the surface, but may be useful as an irritant. define $N(m,n,k)$ to be the number of ways $n$ things can be each painted one of $m$ colors with exactly $k$ of them uniquely colored.
also set 
$$
Z(m,n) = N(m,n,0)
$$
then
$$
N(m,n,k) = \binom{n}{k}Z(m-k,n-k)
$$
perhaps this draws attention to the importance of dealing first with the slightly simpler problem of finding the $Z(m,n)$?
A: This problem is essentially a variation of the "Coupon Collector's Problem".  It can be solved by the "Generalized Inclusion / Exclusion Principle". (Reference: Applied Combinatorics by Alan Tucker; I am afraid my edition is so old that a page number would not help.)
If we draw the $n$ Xs one at a time, there are $m^n$ possible outcomes, each of which we assume is equally likely.  We will count the number of arrangements in which exactly $k$ numbers are missing, i.e. the number of distinct numbers drawn is $m-k$.
Let's say an arrangement has "Property $i$" if the number $i$ is not among the numbers drawn.  Define $S_j$ as the number of arrangements with $j$ of the properties, i.e. missing $j$ of the $m$ possible numbers.  Then
$$\begin{align}
S_1 &= \binom{m}{1} (m-1)^n \\
S_2 &= \binom{m}{2} (m-2)^n \\
&\dots \\
S_{m-1} &= \binom{m}{m-1} (1)^n \\
S_m &= 0 \\
\end{align}$$
By the Generalized Inclusion / Exclusion Principle, the number of arrangements with exactly $k$ of the properties is
$N_k = S_k - \binom{k+1}{k} S_{k+1} + \binom{k+2}{k} S_{k+2} - \dots + (-1)^{m-k} \binom{m}{k} S_m$
So the probability that there are exactly $k$ numbers missing from the arrangement, i.e. the number of distinct numbers drawn is $m-k$, is $$\frac{N_k}{m^n}$$
This formula gives you a theoretical means of computing the distribution of the distinct numbers drawn, but for large values of $n$ and $m$ it may be difficult to compute in practice, due to the huge binomial coefficients involved.  I don't know an easy solution to the computational difficulties.
