2
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ What do you mean with p'th element of A cannot get mapped on p'th element of B? This seems to imply that there is an order induced on the sets $A,B$? Can you provide the full question? $\endgroup$ – user370967 Sep 23 '17 at 11:35
  • $\begingroup$ 1st element of A cannot be mapped with 1st element of B. $\endgroup$ – Zephyr Sep 23 '17 at 11:36
  • 2
    $\begingroup$ It might be more handsome to set $A=\{1,2,3\}$ and $B=\{1,2,3,4,5\}$. $\endgroup$ – drhab Sep 23 '17 at 11:37
  • $\begingroup$ But, there is no order in a set. For example, $ \{1,2\}$ and $\{2,1\}$ are exactly the same sets $\endgroup$ – user370967 Sep 23 '17 at 11:38
  • 1
    $\begingroup$ in non ordered sets though there isn't really a first element the sets$\{1,2,3\},\{1,3,2\},\{2,3,1\},\{2,1,3\},\{3,1,2\}$ and $\{3,2,1\}$ are all the same set. $\endgroup$ – user451844 Sep 23 '17 at 11:38
2
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Thanks a lot for the explanation ! $\endgroup$ – Zephyr Sep 23 '17 at 16:32
  • 1
    $\begingroup$ When we apply the Inclusion-Exclusion Principle, we first exclude cases in which there is one corresponding element. Notice I did not say exactly one. Each map in which there are exactly two corresponding elements is subtracted twice and each map in which there are exactly three corresponding elements is subtracted three times. The first step in correcting that count is to add those cases with two corresponding elements back (including those with exactly three corresponding elements). The final step is to subtract the case with three corresponding elements (see the last paragraph). $\endgroup$ – N. F. Taussig Sep 28 '17 at 8:04
  • 1
    $\begingroup$ Let's consider the map $1 \mapsto 1$, $2 \mapsto 2$, and $3 \mapsto 4$. It has exactly two corresponding elements, $1$, and $2$. We count this map once when we designate $1$ as the corresponding element and once when we designate $2$ as the corresponding element. On the other hand, the map $1 \mapsto 1$, $2 \mapsto 2$, and $3 \mapsto 3$ has exactly three corresponding elements. We count it three times, once for each of the three ways we could designate one of the three elements in $A$ as the corresponding element. $\endgroup$ – N. F. Taussig Sep 28 '17 at 8:44
  • 1
    $\begingroup$ I appreciate your patience. Thanks ! $\endgroup$ – Zephyr Sep 28 '17 at 8:54
  • 1
    $\begingroup$ @Zephyr Your persistence and willingness to ask questions will serve you well as you continue your studies. $\endgroup$ – N. F. Taussig Sep 28 '17 at 9:55
-1
$\begingroup$

Since you have 5 different choices for 3 different numbers. The first element in A has 5 choices from B. Now, as the first element has chosen one element in B, you will only have 4 choices left in B. So, the second element only has 4 choices from b. And, the final element will have 3 choices. By the principle of multiplication, There are 5*4*3 = 60 total injective functions.

This can be summed up as |A||B|.

Hope that helped.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.