The number of injective functions possible from A to B such that p'th element of A cannot map with p'th element of B where |A|=3 and |B|=5 is ?
My attempt:-
Total number of injective functions possible from A to B = 5!/2! = 60.
1) Number of ways in which one element from set A maps to same element in set B is
(3C1)*(4*3) = 36.
2) Number of ways in which two elements from set A maps to same elements in set B is
(3C2)*(3) = 9.
3)Number of ways in which three elements from set A maps to same elements in set B is 1
So, answer should be 60-(36+9+1) = 14.
But it seems that my answer is wrong. Can someone point out the mistake in my approach ?
Best Answer
For clarity, let $A = \{1, 2, 3\}$ and let $B = \{1, 2, 3, 4, 5\}$, as @drhab suggested.
You did not apply the Inclusion-Exclusion Principle correctly.
The correct answer is $60 - 36 + 9 - 1 = 32$.
When we subtract those cases in which one element of $A$ is mapped to the corresponding element of $B$, we have subtracted those cases in which two elements of $A$ are mapped to corresponding elements of $B$ twice, once for each way we could designate one of those elements as the element of $A$ that is mapped to the corresponding element of $B$.
Since we only want to exclude those cases in which two elements of $A$ are mapped to corresponding elements of $B$ once, we must add those cases back.
However, we have not excluded the case in which all three elements of $A$ are mapped to the corresponding elements of $B$ since we subtracted them three times, then added them three times. We subtracted them three times when we counted those cases in which one element of $A$ is mapped to the corresponding element of $B$, once for each way we could designate one of the three elements as the one that is mapped to the corresponding element of $B$. We added them three times when we counted those cases in which two elements of $A$ are mapped to the corresponding elements of $B$, once for each of the $\binom{3}{2}$ ways we could designate two of the three elements as the elements of $A$ that map to the corresponding elements of $B$. Therefore, we must subtract the case in which all three elements of $A$ are mapped to the corresponding elements of $B$.