calculate expected collision count Let's say I have a uniformly distributed random number sequence whose values are in the range [1, m]. Each value has a chance of p = 1/m appearing. Take a sample of size s from that sequence. For a given value in the sample, let n be the number of duplicates in the rest of the sample. Let c be the count of numbers in the sample that have the same n.
For example:

*

*if n = 0, then c is the number of unique values in the sample.

*if n = 1, then c is the number of values that have one same value in the rest of the sample.

So for a given n, how to calculate the expected c?
Below are some simulated results.
for m = 65536, s = 1000




n
c




0
978


1
22


2
0




for m = 65536, s = 10,000




n
c




0
8598


1
1284


2
114


3
4


4
0




for m = 65536, s = 100,000




n
c




0
21806


1
33326


2
24915


3
13076


4
4865


5
1566


6
350


7
96


8
0



 A: The mathematical content behind this question has already been answered here:
Sampling with replacement - Expected number of duplicates, triplicates, ..., n-tuples
However, the phrasing is slightly different, so let me help translate. In this problem, we have a sequence of random variables $X_1,\ldots,X_s$, where each $X_i$ is uniformly distributed in $\{1,\ldots,m\}$, and we wish to compute the expected number of $X_i$'s which are unique ($n=0$), repeat exactly twice ($n=1$), and so on, for all $n$.
In the question I linked to above, the names of the variables are different but it is the same mathematical setup. The $m$ in our problem here, is the genome size in the other question. The $s$ in our problem here, is the sample size of the number of genes in the other question. Rephrasing the answer of https://math.stackexchange.com/users/6460/henry in this notation, the probability of seeing a particular value of $X_i$ exactly $k$ times is
$$
\binom{s}{k}\frac{(m-1)^{s-k}}{m^s}
$$
and therefore the expected number of indices $i$ such that the value $X_i$ appears exactly $k$ times is
$$
k\binom{s}{k}\frac{(m-1)^{s-k}}{m^{s-1}}.
$$
A value that appears exactly $k$ times corresponds to an $n$ value of $k-1$ in the notation of this question, so we obtain the formula:
$$
\mathbb E[c_n]=(n+1)\binom{s}{n+1}\frac{(m-1)^{s-n-1}}{m^{s-1}}
$$
A: Let $X_i$ denote the number of values in the sequence that take on value $i$, where $1 \leq i \leq m$, and let $Z_n$ the number of values in the sequence that are the duplicate of exactly $n$ other values.
What we're interested in computing is $\mathbb{E} Z_n$, where
$$ Z_n = \sum_{i=1}^m (n+1)\mathbb{1}\{X_i=n+1\}.$$
By linearity of expectation, this is
$$\mathbb{E}Z_n = \sum_{i=1}^m (n+1)P(X_i=n+1)=m(n+1)P(X_1=n+1).$$
Since $X_i\sim \text{Binom}(s,1/m)$, we have
$$P(X_1=n+1)=\binom{s}{n+1} \left(\frac{1}{m}\right)^{n+1}\left(1-\frac{1}{m}\right)^{s-n-1},$$
therefore
$$\mathbb{E}Z_n = (n+1)\binom{s}{n+1}\left(\frac{1}{m}\right)^{n}\left(1-\frac{1}{m}\right)^{s-n-1}.$$
For m = 65536, s = 100,000:




n
c
$\mathbb{E}Z_n$




0
21806
21743.1


1
33326
33177.5


2
24915
25312.3


3
13076
12874.3


4
4865
4911.1


5
1566
1498.7


6
350
381.1


7
96
83.1


8
0
15.8



