Insertion in Hash table. (M.E.)

Question

The number of different insertion sequences of numbers $\left \{ 7,20,32,50,66,77 \right \}$ on an initially empty hash table H of size $6$ and a hash function $h\left ( k \right )=k\mod6$ with linear probing scheme for collision resolution such that the hash table obtained after the insertion looks as shown in fig below is equal to ______________________

66

7

20

32

50

77

     ${\color{Blue} {0}}$.                  ${\color{Blue} {1}}$               ${\color{Blue} {2}}$                      ${\color{Blue} {3}}$.                       ${\color{Blue} {4}}$                     ${\color{Blue} {5}}$

 

 

Comments

$120\,?$

---

how @Shobhit Joshi

I have done like this 

22------32---------50 in 1 sequence

66 and 7 are parallel with these three

So, in ordering if we do parallel 66,7,22 in 3! ways i.e. 6 ways.......................i

And 77 can come in any order with other 5 numbers, So, it comes in 6 ways---------------ii

So, 6*6=36

tell me your approach

where I gone wrong?

---

7, 66 , 77  and the set { 20,32,50} can come in any order and in the set order should be maintained (20-> 32 -> 50)

so 6!/3! = 120.

---

@srestha (20,32,50),77,66,7 arranging them would take $\frac{6!}{3!}=120$, as the order of (20,32,50) should be maintained

---

66, 77, 7 are free they can come anywhere in any order.

$20\rightarrow 32\rightarrow 50$  this order has to be maintained.

Out of 6 places choose 3 and then place 66,77,7 in 3! ways. And 20,32,50 can be placed in obly one way.

$\implies ^6C_3 * 3!= 120$

---

@srestha

22------32---------50 in 1 sequence

66 and 7 are parallel with these three

So, in ordering if we do parallel 66,7,22 in 3! ways i.e. 6 ways..................

ma'am if we try to do like this then we might miss out some possibilities..

eg:- __22__32__50__ in this order in blanks if we fill 66 and 7 then we get 12 ways.(in none of these arrangement we get 66 and 7 together,,).. I feel solving this way lead to more cases( little complex)..

@Shobhit Joshi @Satbir easiest solution..👌

---

@Shobhit Joshi how it is coming 6! as 3 elements and 1 set is there  so shoud nt it be 4??

 

---

6! factorial is for total combinations possible with 6 elements.

---

ohh so it finally reduces to problem of 6 elements with 3 to come in a specific sequence... got it thanks :)

Answer 1

final result be like this -

index        elements 

0                  66

1                  7

2                  20

3                  32

4                  50

5                  77

input sequence = {7, 20, 32, 50, 66, 77}

h(k)=k mod 6          |    |    |    |     |    |

                                   v    v    v    v      v    v     

                                   1    2   2    2     0    5

So therefore order of there coming can be 

66, 77, 7 are independent  they can come anywhere in any order.

20→32→50  this order has to be maintained.

out of 6 3 places has to chooses and then rest 3 places any  order 

i.e.  6C3 * 3! = 120.

  

 

Answer 2

66,7,77 can come in anytime.

Order for these:20-> 32-> 50

Think of these as 4 schedules.

No of schedule possible = 6!/3! (As 3 are in same schedule so no reordering possible)

                                             = 120

Wrong approach:

Trying to make 20-> 32 -> 50 as a group and trying to solve it like abc must come together combination problem.

Here answer is 4!.

Why wrong?

Here 20,32,50 needn't be consecutive so we cannot solve it that way.

Answer 3

in my opinionwhat I have undestood that sequence number asked is 6! =720 nos