Consider a multiset $S=\{a\_1,a\_2,...,a\_{2n}\}$ of natural numbers. There are $2n$ elements (not necessarily unique since $S$ is a multiset) in $S$. All elements of $S$ belong to a set of natural numbers $R$ with size $N$ (i.e |R|=N). The probability that a number $i$ is in the multiset $S$ is $P\_i$. Each element $a\_i$ is independent identically distributed over the set $R$. Now let's consider a matrix with $n$ columns and arbitrary number of rows. If we want to put all elements of $S$ in the matrix in such a way that no same elements are on the same row, how many average number of rows do we need? 


For example if all $2n$ elements of the multiset are unique, we need 2 rows to fit all elements in the matrix and if all $2n$ elements are same, we need $2n$ rows. 


[note: I asked this question on mathstack exchange but did not get any answer] 



Average number of rows to fit all elements in a multiset of natural numbers
You are selecting iid random variables $a\_1, \ldots, a\_{2n}$ from some distribution. And you want to estimate how often the most common value appears.


Let $p\_{0}$ be the highest probability. If this is much larger than the rest of the values, then $p\_{0} 2n$ is a good estimate (always a lower bound for what you want). If all the values are about equal, then perhaps about $p\_{0} 2n \log(1/p\_{0})$ or so.


