Изменения

Пусть хеш-таблица имеет размер <tex>len</tex> и в нее добавляют <tex>n</tex> элементов. Рассмотрим <tex>{p}'(n)</tex> - вероятность того, что не возникнет ни одной коллизии. Добавим два любых элемента в нашу хеш-таблицу. Вероятность того, что они не попадут в одну и ту же ячейку таблицы равна <tex>1 - \fracdfrac{1}{len}</tex>. Возьмем еще один элемент. Тогда вероятность того, что третий элемент не попадет в одну из уже занятых ячеек равна <tex>1 - \fracdfrac{2}{len}</tex>. Рассуждая аналогичным образом, получим формулу:<tex>{p}'(n) = \left( 1 - \fracdfrac{1}{len}\right )\cdot \left( 1 - \fracdfrac{2}{len}\right )\dots\left( 1 - \fracdfrac{n - 1}{len}\right ) = \fracdfrac{len \cdot \left(len - 1 \right )\dots\left (len - n + 1 \right )}{len^{n}} = \fracdfrac{len!}{len^{n} \cdot \left (len - n \right)!}</tex>