Sinto que estou pensando demais neste problema, mas aqui vai mesmo assim ...

Tenho uma tabela de hash com slots M em sua matriz interna. Eu preciso inserir N elementos na tabela de hash. Supondo que eu tenha uma função hash que insira aleatoriamente um elemento am em um slot com probabilidade igual para cada slot, qual é o valor esperado do número total de colisões de hash?

(Desculpe, isso é mais uma questão de matemática do que uma questão de programação

Edit: Aqui está um código que eu tenho que simular usando Python. Estou recebendo respostas numéricas, mas estou tendo problemas para generalizá-la para uma fórmula e explicá-la.

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