title: Probability of Collisions in Hash Table
body: <p>When inserting n items into a hash table of size m, assuming that the destination of each item is independently uniformly random, what is the probability that no collision occurs?</p>
  
  <hr>
  
  <p>My working thus far:
  We have n items and m locations.
  Each item has a 1/m chance of being in any particular location.
  There are nC2 possible pairs of items.
  The probability of there being no collisions is the probability that for every location, every pair of items does not hash to that location. </p>
  
  <p>For any given location, for any given pair, the probability that the two items do not hash to that location is (m-1)/m.</p>
  
  <p>Then, for any given location, the probability that the above is true for ALL pairs is ((m-1)/m)^(nC2).</p>
  
  <p>Then, the probability that this is true for every location is
  [((m-1)/m)^(nC2)]^(m).</p>