Made Easy Test Series:Algorithm-Mathematical Solution

Question

Consider a hash table with $n$ slots that uses chaining for collision resolution, table is initially empty. What is the probability that after $4$ keys are inserted then atleast a chain of size $3$ is created, when the value of $n=9$___________

---

They have done like 

Chain of size $4$ is  $1\times \frac{1}{n}\times \frac{1}{n}\times \frac{1}{n}=\frac{1}{n^{3}}$

and Chain of size $3$ is  $1\times \frac{1}{n}\times \frac{1}{n}\times \frac{n-1}{n}=\frac{n-1}{n^{3}}$

but my question is , why will it not Chain of size $4$ is  $ \frac{1}{n}\times \frac{1}{n}\times \frac{1}{n}\times \frac{1}{n}=\frac{1}{n^{4}}$

and same for chain of size $3??$

Plz chk it

Comments

The probably of chain of size 3 will be 4c3 (n-1) cube divided by n cube

Answer 1

The first one to enter the hash table can choose any slot right?
So the probability of 1st one to get a slot = $n/n = 1$.

Now for chain of 4 , the remaining three needs to get the same slot as the 1st one one , thus has only one choice.

Therefore , chain of 4 = $1*(\frac{1}{n})^{3}$.

For chain of 3, any one of the remaining 3 must not get the same slot .

so one of them must choose slots with a probability of $\frac{n-1}{n}$.

And Total probability of getting a chain of 3 will be $\frac{n-1}{n^{3}}$.


Thus total probability will be = Chain of 4 + Chain of 3 = $(\frac{1}{n})^{3}+\frac{n-1}{n^{3}}$.