The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
154 views

The number of ways possible to form injective function from set A to set B where |A| = 3 and |B| = 5 such that $p^{th}$ element of set A cannot match with $p^{th}$ element of set B are _________.

My Attempt:

The solution to this one will be like below

Total number of injective functions from 3 element set to 5 element set - Total number of injective functions in which either the first, or second or third element from set A matches with their respective element in Set B.

So, Total number of injective functions from a 3 element set to a 5 element set = $5P_3=60$

Now Case 1: Element $i$ matches with $i^{th}$ element of set B- Number of ways to select this $i^{th}$ element=$3C_1$ and now number of injective functions from 2 element set to 4 element set=$4P_2$. So total ways=$3C_1*4P_2=36$

Case 2: Element $i$ and $j$ match with $i^{th}$ and $j^{th}$ element of the set B.-Number of ways to select $i,j=3C_2$ and now number of injective functions from a 1 element set to a 3 element set = $3P_1$. So total ways here=9.

Case 3: Element $i,j,k$ match respectively with their elements in Set B.-Only 1 way.

So, total number of injective functions from a 3 element set to a 5 element set in which $p^{th}$ element of set A matches with $p^{th}$ element of set B=36-9+1 (By inclusion-exclusion principle)=28

So, my final answer should be 60-28=32

But they have given the solution like this below

 

 

I think in case 2, it should be like $3C_2*3P_1$ instead of $4P_1$ because after $i^{th}$ and $j^{th}$ elements are mapped to their respective elements, now only 1 element from Set A need to be mapped to remaining 3 elements in Set B, considering that function has to be injective, so total ways must be 3.

What should be the correct way?

asked in Calculus by Boss (24.8k points)
recategorized by | 154 views
0

Ayush Upadhyaya, yes your way is right

 

but i have doubt that, cases are not overlapped?

i mean, n(A U B U C) = n(A)+n(B)+n(C) - n(A ∩ B) - n(B ∩ C) - n( A ∩ C) + n(A  ∩ B ∩ C )

A---> case 1 :- i is matched with i

B---> case 2 :- i is matched with i and j is matched with j 

C---> case 3 :- i is matched with i and j is matched with j and k is matched with k

0
@Shaik-No they are. Case 1 makes sure element i surely matches with i and all other can match with anyone.

Case 2 makes sure i and j match with i and j and rest with anyone. So, there might be a case in case 1 where i matches with i and among the rest j also matches with j.
0
in case 1:-

let 1 is matched with 1===> in all possible cases, just take in any case 2 is matched with 2

 

in case 2:-

let 1 is matched with 1 and 2 is matched with 2 ===> didn't overlap with case1 ?
0

This case will come under case 1 and case 2 both

0

That's what i am saying also...

there are some possibles counted more than once... 

therefore you have to use this formula n(A U B U C) = n(A)+n(B)+n(C) - n(A ∩ B) - n(B ∩ C) - n( A ∩ C) + n(A  ∩ B ∩ C )

0
yes it should be 32.
0
But i am getting 36+9+1-9-1-1+1 ( terms with respect to formula ) = 36

Required =  60-36 = 24. ... Correct me if i am wrong
0
YES i am getting ans 32 too. I guess it is correct!!
0
can you share your answer?

1 Answer

+2 votes
Best answer

We can solve this problem easily by using Inclusion-Exclusion principle.

First we will count the number of onto functions where at least one element of $A$ maps to the corresponding element of $B.$

$|1 \cup 2 \cup 3|= |1| + |2| + |3| - |1 ∩ 2| - |1∩3| - |2∩ 3| + |1∩ 2 ∩ 3|$
where, $|x|$ represents no. of possible functions in which $x^{th}$ element of $A$ is mapped to $x^{th}$ element of $B.$

Lets consider the case where first element from set $A$ is mapped to first element of set $B.$

First element of $A$ can be mapped to first element of $B$ in only $1$ way.

Now, in calculating the total number of functions where this happens, $2^{nd}$ and $3^{rd}$ elements can be mapped to in $4\times 3$ ways and not $4\times 4$ as we are forming one-one functions and not general functions.

So, total no. of functions in which $1^{st}$ element of $A$ is mapped to the first element of $B$ $= 1\times 4\times 3=12.$

Similarly for $|2|$ and $|3|$ also we will get $12$ ways. So, $|1| + |2| + |3|= 36.$

 Now,  $|1 ∩ 2| =$ number of one-one functions where $1$ and $2$ are mapped to first and second elements respectively.

$=1\times 1 \times 3.$

Similarly, $|1 ∩ 2| = |1 ∩ 2|=3$ and $|1∩ 2 ∩ 3|=1.$

So, $|1 \cup 2 \cup 3 |=36-9+1=28.$

Total no. of one-one functions possible from $A$ to $B=5\times 4\times 3=60.$

Hence, our required answer $= 60-28=32.$

answered by Loyal (7.6k points)
selected by
0

@shaik

therefore you have to use this formula n(A U B U C) = n(A)+n(B)+n(C) - n(A ∩ B) - n(B ∩ C) - n( A ∩ C) + n(A  ∩ B ∩ C )

formula used above is same only...its way of writing it differently..

the selection which we are doing i.e 3C1(n(A)+n(B)+n(C)) is too consider for all 3 elements

same for two elment case we  are doing 3C2..

and answer is 32 i guess its correct..!

0
@ayush

yes in second case it should be 3P1 not 4C1...your answer is correct..!

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
49,808 questions
54,481 answers
188,251 comments
74,527 users