How to count the number of types I have a problem which has come up from a computer simulation I am writing. There is a multiset $\{a_1, a_2,\dots, a_n\}$ of integers. For uniformly and independently chosen $1\leq i,j \leq n$ I know exactly $P(a_i = a_j)$. What does this tell me about the number of distinct $a_i$?
If $P(a_i = a_j) = 0$ then clearly all the $a_i$ are distinct. Similarly, if $P(a_i = a_j) = 1$ they are all the same. However,  for other values of $P(a_i = a_j)$ I can't work out what exactly it tells you about the number of distinct $a_i$.
 A: Suppose there are $k$ distinct values, with $n_i$ of each type (where $i\in\{1,\dots,k\}$). We can create a graph on the $n$ vertices $\{1,\dots,n\}$ where there is an edge from $i$ to $j$ iff $a_i=a_j$. Then since equality is transitive, we will get a complete graph on each subset that is equal to one of the $k$ different values, so the overall structure is a disconnected collection of complete graphs of different sizes, and $P(a_i=a_j)$ is just $\frac1{n^2}$ times twice the number of edges in the graph, plus $n$, since we count $i=j$ and also count $i,j$ and $j,i$ separately. When all the $a_i$'s are distinct, this is a set of $n$ disconnected points, so there are no edges and $P(a_i=a_j)=P(i=j)=\frac1n$ (not 0, as you claim). When there are $n-1$ distinct values, there is one edge in the graph, so  $P(a_i=a_j)=\frac1n+\frac2{n^2}$.
Beyond this, there is some variation, because the number of edges in the graph is not uniquely determined by the number of connected components. If we know the full distribution of sizes of the components $n_i$ (where $\sum_{i=1}^kn_i=n$), then there are $|Edges(K_{n_i})|=\frac{n_i(n_i-1)}2$ edges in each subgraph, so $P(a_i=a_j)=\frac1n+\sum_{i=1}^k\frac{n_i(n_i-1)}{n^2}$. It is possible to bound the size of this quantity, though, given only $k$.
Since large groups have more edges per vertex than small groups, upper bounds on the number of edges come when there is one large group, and a bunch of isolated vertices. In this case, $n_1=n-k+1$ and $n_2=\dots=n_k=1$, so $$P(a_i=a_j)\le\frac1n+\frac{(n-k+1)(n-k)}{n^2}.$$ In the lower bound, all the groups are of equal size, that is $n_i=n/k$, so $$P(a_i=a_j)\ge\frac1n+\frac{n(n-k)}{kn^2}=\frac1k.$$
In your situation, $P(a_i=a_j)$ is known, but $k$ is not, but you can still use these bounds to find the highest and lowest values of $k$ that allow your known value of $P(a_i=a_j)$, by solving the above equations for $k$.
A: I've upvoted Mario Carneiro's answer, but I'm posting an answer anyway to make it clearer.
Suppose there are $k$ distinct values, with $n_i$ ocurrences of the $i$th value, so that $$n_1 + n_2 + \dots + n_k = n. \tag 0$$
Then, the probability over uniformly and independently chosen $(i, j)$ that $a_i = a_j$ is
$$\frac1{n^2}(\text{number of pairs $(i, j)$ such that $a_i = a_j$}) = \frac{1}{n^2}(n_1^2 + n_2^2 + \dots + n_k^2)$$
That's it. That is all the information that you have. If you calculate the probability as $p$, then you're trying to find $k$ such that for some (positive integral) choices of $n_1, n_2, \dots, n_k$ with $n_1 + n_2 + \dots + n_k = n$, we have
$$n_1^2 + n_2^2 + n_3^2 + \dots + n_k^2 = n^2 p \tag 1$$
(which better be an integer). This becomes a number-theory problem now. If $n$ is small, you could brute-force over all possible such tuples, to find all values of $k$ for which solutions to $(0)$ and $(1)$ exist.
For example, from the Cauchy-Schwarz inequality, we have
$$(n_1^2 + n_2^2 + \dots + n_k^2)(1^2 + 1^2 + \dots + 1^2) \ge (\sum n_i)^2 \implies n^2pk \ge n^2$$ 
(attained when all $n_i$ are equal), so 
$$k \ge 1/p \tag 2$$
In the other direction, the sum of squares is maximized when we have one value as large as possible: that's $(k-1)$ ones and one $n-(k-1)$, so the sum of squares is 
$$n^2p \le (n-k+1)^2 + (k-1)$$ giving
$$k \le \frac12 (2n + 1 - \sqrt{4n^2p - 4n + 1}) \tag 3$$
but of course better bounds may be possible, exploiting number-theoretic properties.
