Siento que estoy pensando demasiado este problema, pero aquí va de todos modos ...

Tengo una tabla hash con ranuras M en su matriz interna. Necesito insertar N elementos en la tabla hash. Suponiendo que tengo una función hash que inserta aleatoriamente un elemento en una ranura con la misma probabilidad para cada ranura, ¿cuál es el valor esperado del número total de colisiones hash?

(Lamento que esto sea más una pregunta matemática que una pregunta de programación).

Edit: Aquí hay un código que tengo para simularlo usando Python. Recibo respuestas numéricas, pero tengo problemas para generalizarlo a una fórmula y explicarlo.

import random
import pdb

N = 5
M = 8

NUM_ITER = 100000

def get_collisions(table):
    col = 0
    for item in table:
        if item > 1:
            col += (item-1)
    return col

def run():
    table = [0 for x in range(M)]

    for i in range(N):
        table[int(random.random() * M)] += 1

    #print table
    return get_collisions(table)

# Main

total = 0
for i in range(NUM_ITER):
    total += run()

print float(total)/NUM_ITER