Given that A hash table contains 'n' buckets, Chaining is used to resolve the collisions and Initially Hash table is Empty.
The Probability that a key value is hashed to a particular bucket is $\frac{1}{n}$
we need to insert K distinct values into the hash table.
there are 'n' buckets, named as bucket 1, bucket 2, bucket 3,..... bucket 'n'
A) What is the probability that bucket number 1 is empty after the K$^{th}$ insertion?
after inserting one value in to the hash table, what is the probability that " bucket 1" is empty ?
there are "(n-1)" buckets excepts bucket 1, So it lead to $\color{red}{(\frac{n-1}{n})}$
after inserting second value in to the hash table, what is the probability that " bucket 1" is empty ?
there are "(n-1)" buckets excepts bucket 1 ( we don't care even it is collision in other bucket ) , So it lead to $\color{red}{(\frac{n-1}{n})}(\frac{n-1}{n})$
after inserting third value in to the hash table, what is the probability that " bucket 1" is empty ?
there are "(n-1)" buckets excepts bucket 1, So it lead to $\color{red}{(\frac{n-1}{n})^2}(\frac{n-1}{n}) = \color{red}{(\frac{n-1}{n})^3}$
after inserting K$^{th}$ value, probability that " bucket 1" is empty = $\color{red}{(\frac{n-1}{n})^{(K-1)}}(\frac{n-1}{n}) = \color{red}{(\frac{n-1}{n})^K}$
B) What is the probability that no collision has occurred in any of the K insertions?
for inserting one value in to the hash table, we have 'n' buckets ==> map to any bucket = $\color{red}{n}.\frac{1}{n}$
for inserting second value in to the hash table, we have '(n-1)' buckets due to the previously mapped bucket we can't use = $\color{green}{\frac{n}{n}}.\color{red}{(n-1)}\frac{1}{n}$
for inserting third value in to the hash table, we have '(n-2)' buckets due to the previously mapped bucket we can't use = $\color{green}{\frac{n}{n}}.\color{green}{\frac{(n-1)}{n}}.\color{red}{(n-2)}.\frac{1}{n}$
........
for inserting (K-1)$^{th}$ value in to the hash table, we have '(n-(k-2))' buckets due to the previously mapped bucket we can't use =
$\color{green}{\frac{n}{n}.\frac{(n-1)}{n}.\frac{(n-2)}{n}.....\frac{(n-(K-3))}{n}}..\color{red}{(n-(K-2))}\frac{1}{n}$
for inserting K$^{th}$ value in to the hash table, we have '(n-(k-1))' buckets due to the previously mapped bucket we can't use = $\color{green}{\frac{n}{n}.\frac{(n-1)}{n}.\frac{(n-2)}{n}.....\frac{(n-(K-2))}{n}}..\color{red}{(n-(K-1))}\frac{1}{n}$
Note :-
if K > n, then there should be collision.
C) What is the probability that the first collision occurs at the K$^{th}$ insertion?
so upto K-1 we don't have any collision... and at K$^{th}$ insertion we have to collision.
for collision at K$^{th}$ insertion, we have to choose any (K-1) buckets which are previously mapped.
= $\color{green}{\frac{n}{n}.\frac{(n-1)}{n}.\frac{(n-2)}{n}.....\frac{(n-(K-2))}{n}}..\color{red}{(K-1)}\frac{1}{n}$
Note :-
if K = n+1, then it must be collision. So K > n+1 can't be the first collision