Ожидаемое количество хеш-коллизий

Я чувствую, что переосмысливаю эту проблему, но все равно ...

У меня есть хэш-таблица с М слотов во внутреннем массиве. Мне нужно вставить N элементов в хэш-таблицу. Предполагая, что у меня есть хеш-функция, которая случайным образом вставляет элемент am в слот с равной вероятностью для каждого слота, каково ожидаемое значение общего числа коллизий хеша?

(Извините, что это больше вопрос математики, чем вопрос программирования).

Изменить: Вот код, который я должен имитировать с помощью Python. Я получаю числовые ответы, но не могу обобщить их в формулу и объяснить.

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

Ответы на вопрос(2)

Ваш ответ на вопрос