Discrete Maths

Question

How many one to one functions are possible from A to B where |A| =4 and |B| = 6 such that i^th element of A can not match with i^th element of B.??

Comments

Take a small example A={1,2} and B={1,2,3}

and here also the same condition : ith of A should not match with ith of B .

according to your method : 1st element of A is having 2 choices and 2nd element of A is having 1 choice. so total possible = 2*1 =2

But actually possible functions are 3 :

first case : 1->2 , 2->1
second case: 1->2 , 2->3
third case: 1->3 , 2->1

---

Ty Amit for pointing out..this means ans should be more than 120 as we need to consider some extra possibilities also

---

I think inclusive-exclusive principle will give correct ans??
$=\ ^6P_4-(^4C_1\ ^5P_3\ -\ ^4C_2\ ^4P_2\ +\ ^4C_3\ ^3P_1 \ -\ ^4C_41)\\ =360-(240-72+12-1)\\ =360-179\\ =181$

---

Yes, got the same answer.

Answer 1

Given that ith element of A set cannot be mapped with ith element of B set..So i can range from 1 to 4 i.e one of the 4 values of i..

So we first select that in C(4,1) ways  =  4 ways..

Now we are left with 3 elements in A and 5 elements in B..

So for the above constraint i.e. 3 elements in A and 5 elements in B ,

We have no of one one functions  =  ⁵P₃  =   5! / 2!   =   60

So no of one one functions from A to B with A having 4 elements and B having 6 elements 

with the given constraint              =  4 * 60

                                                 =   240

But these are the functions in which ith tuple of A matches with ith tuple of B.

And total no of one one functions possible  =  ⁶P₄

                                                               =  720 / 2   = 360

So no of required functions in which ith tuple does not match  =   360  -  240

                                                                                          =   120

Hence 120 should be correct answer..

Comments

How you are taking care of the condition that ith element of A should not match ith of B . IN 5P3 . , those case will be there when ith of A is matched to ith of B . correct me if i am wrong

---

if both the set having 6 elements what will be the ans ??

---

then that will be the dearrangment case for 6 elements .

---

Edited bro ..Plz check..

---

yah ...i'm trying to apply dearrangement in this problem !

given the above problem can be solved with Dearrangement ..by some modification...i'm tryinn...

---

Habib bro , what is your appraoch ? first you are fixing one ith element of A to ith element of B and placing rest of 3 element in 5 position ?  but i think in this some cases will be repeated .

---

Total possible one-one functions = 6C4 * 4! = 360

case1: single element of A maps to its proper place

Single element can  be selected in 4C1 ways.

For the remaining 3 elements of A, 3 elements of B can be selected in 5C3 ways and one-one functions from 3 elements of A to 3 elements of B is 3!

Thus, total = 4C1 * 5C3 * 3! = 240

case2: 2 elements of A map to its appropriate position.

select 2 elements of A = 4C2 ways

select 2 elements of B for remaining 2 elements of A = 4C2 ways

2 elemenets of A to 2 elements of B one-one functions = 2!

Thus, total = 4C2 * 4C2 * 2! = 72

case3: 3 elements maps to their appropriate place

select 3 elements of A = 4C3 ways

select 1 element of B for remaining 1 element of A = 3C1 ways

1 elemenet of A to 1 element of B one-one functions = 1!

Thus, total = 4C3 * 3C1 * 1! = 12

case4: all 4 elements of A map to their appropriate positions

This can be done in only 1 way.

Thus, answer

= 360 - [240 - 72 + 12 -1]

= 181

---

@ sushant . in your first case , it might be possible that all element from A will match to ith of B in 5c3*3! . how you can say only one will be matched to it of B .

---

@Amit Pal.

Yes possible.

But repetitions will be eliminated. Dont worry....thats beauty of inclusion-exclusion.

A simple thing to remember is the formula we apply for counting total functions( i.e 6C4 * 4! ) is also applied when we consider inclusion-exclusion.

---

Yes Sushant , that i understood as we apply the same approach in calculation of on to funtions possible .
but wanted to hear your confirmation .

Thanks!

---

@sushant nice explanation