The number of different insertion sequences on the numbers

Question

The number of different insertion sequences on numbers {1, 14, 26, 44, 60, 71} on an initially empty hash table H of size 6 and a hash function x%6 with linear probing scheme for collision resolution such that the end hash table should look like 60, 1, 14, 26, 44, 71 (The indices of numbers from left to right are 0 to 5) are ________

Answer 1

14, 26 and 44 mod 6 = 2 and hence in any input sequence they must come in sequence (otherwise their sequence changes in the end result). The other 3 numbers hash to distinct locations and hence they can be inserted in any order. So, number of possible insertion sequence

$=\frac{\text{Total insertion sequences}}{\text{Invalid insertion sequences}}$

$=\frac{6!}{3!}$

$= \frac{720}{6} = 120$

Comments

@arjun Sir...I have a doubt
If we consider 14,26,44 as a sequence... the other 3 numbers have 4 choices and they can go to one of the 4 places.
So it could be 4*4*4.
Where i am wrong?

---

There are only 6 places. So, other 3 have only 3 places left and actually their places are fixed- only the order of coming can change. Using "place" was bad in my answer- I changed it now- is it clear?

---

I understood your solution but first i thought in some other way as i asked above ...
what is wrong in that method?

---

We have 6 insertions.

So, for 60,1,71 this can be inserted in any of the 6 places (place means order of insertion).

Thus ${}^6P_3 = 120$ ways. Now, other 3 places are taken by 14,26,44 in that order. - Only 1 way possible. So, totally 120 ways.

---

SIR my approach is we have 4 places left so first elemet has 4 choices in such  a way 4*3*2 and these place can be arrange in 4! ways . Now we miss the case in which they together can be place in the 4 remaining  space so  3!*4 in total   120 . Is it right @arjun sir

---

$\binom{6}{3}*1* 3!$   Choosing 3 location from 6 and arranging it only one way i.e 14,26,44 and 3! for arrangement of remaining elements.

---

another way to solve these types of questions is by visualizing using the forest method: https://gateoverflow.in/376398/go-classes-test-series-2023-data-structures-test-question-14