Expected number of uniformly distributed collisions (birthday problem)

Here's an interesting mathematical problem. If you have "n" objects to be inserted into "m" available slots using a uniformly distributed random placement, how many collisions with already occupied slots should we expect to happen? This is useful for hashtables and other data structures where duplicates are not allowed.

Here is a Python 3 program that simulates inserting objects into random positions in an array and counting the average number of collisions.

def collisions(n, m):
 trials = 10000
 total_collisions = 0
 for _ in range(trials):
  slot_is_occupied = [ False for _ in range(m) ]
  for _ in range(n):
   slot = random.randint(0, m-1)
   if slot_is_occupied[slot]:
    total_collisions += 1
   else:
    slot_is_occupied[slot] = True
 return total_collisions/trials

Here is a sample of the average number of collisions given by the above function for different values of "n" and "m":

n\m	1	2	3	4	5	6	7	8	9	10
1	0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.0
2	1.0	0.4947	0.3334	0.2515	0.2054	0.163	0.1437	0.1297	0.1118	0.1053
3	2.0	1.2447	0.8861	0.685	0.557	0.4633	0.4023	0.3537	0.325	0.2819
4	3.0	2.1291	1.5812	1.2588	1.0443	0.9054	0.7754	0.6924	0.6176	0.5459
5	4.0	3.0617	2.4	1.944	1.6457	1.4204	1.2364	1.1123	0.9984	0.9019
6	5.0	4.034	3.265	2.7078	2.304	2.0218	1.7604	1.6004	1.4349	1.318
7	6.0	5.0168	4.1742	3.5406	3.0498	2.6716	2.3973	2.1499	1.9417	1.7744
8	7.0	6.0075	5.1206	4.403	3.8363	3.3905	3.0304	2.7378	2.5151	2.3219
9	8.0	7.0035	6.0765	5.3052	4.6788	4.1652	3.738	3.4168	3.1205	2.8816
10	9.0	8.0016	7.0526	6.2233	5.5401	4.9632	4.493	4.0913	3.7721	3.5016

Basically the answer is the number of objects "n" minus the number of occupied slots. This will give us the number of objects excluding the ones which were inserted without collision, that is, in an empty slot. For example, if I insert 5 objects into an array but at the end there are only 3 occupied slots, then that must mean that 2 of those objects were inserted in the same slot as some other objects (they collided with them).

The question is how to predict the expected number of occupied slots.

Expected number of occupied slots

What is the average number of slots ending up being occupied by at least one object? This previous blog post explains that you basically just need to multiply the probability of a given slot being occupied at the end by the number of slots. So what is the probability of a slot being occupied?

Probability of a slot being occupied

What is the probability that an object is inserted into a particular slot out of "m" slots?
1/m

Therefore the probability that the slot remains empty is
1 - 1/m

What is the probability that the slot is still empty after another placement? It's the probability that the first object did not land on the slot AND that the second object did not land on the slot too. These two probabilities are independent of each other, so
(1 - 1/m)(1 - 1/m)

In general, after "n" objects have been placed, the probability that the slot is still empty is
(1 - 1/m)^n

Notice that this makes sense for n = 0 because if no objects were placed, then the probability that the slot is empty is 1.

Which means that after "n" objects have been placed, the probability that the slot is occupied is
1 - (1 - 1/m)^n

Therefore...

Therefore, the expect number of occupied slots among "m" slots after "n" objects have been inserted with uniform probability is
m(1 - (1 - 1/m)^n)

Which means that the expected number of collisions is
n - m(1 - (1 - 1/m)^n)

Here is the same table as the one at the top showing the corresponding predicted number of collisions:

n\m	1	2	3	4	5	6	7	8	9	10
1	0.0	0.0	0.0	0.0	0.0	0.0	0.0	0.0	-0.0	0.0
2	1.0	0.5	0.3333	0.25	0.2	0.1667	0.1429	0.125	0.1111	0.1
3	2.0	1.25	0.8889	0.6875	0.56	0.4722	0.4082	0.3594	0.321	0.29
4	3.0	2.125	1.5926	1.2656	1.048	0.8935	0.7784	0.6895	0.6187	0.561
5	4.0	3.0625	2.3951	1.9492	1.6384	1.4113	1.2387	1.1033	0.9944	0.9049
6	5.0	4.0313	3.2634	2.7119	2.3107	2.0094	1.776	1.5904	1.4394	1.3144
7	6.0	5.0156	4.1756	3.5339	3.0486	2.6745	2.3794	2.1416	1.9462	1.783
8	7.0	6.0078	5.1171	4.4005	3.8389	3.3954	3.0395	2.7489	2.5077	2.3047
9	8.0	7.0039	6.078	5.3003	4.6711	4.1628	3.7481	3.4053	3.118	2.8742
10	9.0	8.002	7.052	6.2253	5.5369	4.969	4.4984	4.1046	3.7715	3.4868

The maximum absolute error between the two tables is 0.0179.