Relation between size of hashtable and number of values to keep expected number of collisions below/equal to 1

Question

This is an exam question from my algorithms and data structures course.

You imagine an hash function with h: U->{0,..m} (this is from the original question, but i think m-1 would be correct) and n values to hash. You want to keep the expected number of collisions below or equal to 1. How do you determine m in dependence to n.

My initial idea was following formula to determine the number of collisions: $n- E(\text{occupied locations}) = n-m+E(\text{empty locations}) \\$
$= n-m+m(1-\frac{1}{m})^n$

For our question this would give: $ 1 \geq n-m+m(1-\frac{1}{m})^n$

I know that following solution would have been correct (and i know why now):

$E[x]=\frac{n(n-1)}{2} \cdot \frac{1}{m} = m \geq \frac{n(n-1)}{2}$

Well i know i did not solve the first Equation for m (i do not know how), but my question is if both solutions would be correct and if not why?

I got the first Equation from Darthmouth ([Link]:https://math.dartmouth.edu/archive/m19w03/public_html/Section6-5.pdf)

Answer 1

No, your solution is wrong. The expected number of collisions is not $n- E(\text{occupied locations})$, so you went wrong in the first step of your approach. Try working through a small example or two and hopefully you will see why.

It's possible that your confusion has to do with how we count the number of collisions. If items A,B,C all go into the same hash bucket, we consider that as 3 collisions: A,B are a collision, B,C are a collision, and A,C are a collision.