GO Classes DPP | GATE CS | Discrete Mathematics| Functions

Answer 1

First, we handle the condition that exactly two elements in set $B$ have exactly one preimage in set $A$.

• Choose the targets in $B:$ There are $4$ elements in $B$. We need to choose $2$ of them to have exactly one preimage.

  $$\binom{4}{2} = \frac{4!}{2!(4-2)!} = 6 \text{ ways}$$

• Choose the preimages in $A:$ There are $7$ elements in $A$. We need to choose $2$ of them to map to the $2$ selected elements in $B$.

  $$\binom{7}{2} = \frac{7!}{2!(7-2)!} = 21 \text{ ways}$$

• Map them : We have $2$ chosen elements in $A$ and $2$ chosen elements in $B$. There are $2! = 2$ ways to uniquely map them to each other.

For this first phase, there are $6 \times 21 \times 2 = 252$ possible combinations.

 

Now, we have $7 - 2 = 5$ elements remaining in $A$ and $4 - 2 = 2$ elements remaining in $B$.

For the function to be onto, these remaining $5$ elements in $A$ must map to the remaining $2$ elements in $B$. Furthermore, to satisfy the rule that exactly two elements in $B$ have one preimage, neither of these two remaining elements in $B$ can end up with exactly one preimage.

Let's find the number of valid mappings:

• The total number of onto functions from a set of $5$ elements to a set of $2$ elements is $2^5 - 2 = 30$.

• We must exclude any mappings where one of the targets gets exactly $1$ preimage (which means the other gets $4$).

• The number of ways to choose $1$ element from the remaining $5$ to be the sole preimage is $\binom{5}{1} = 5$. Since there are $2$ target elements in $B$ it could map to, there are $5 \times 2 = 10$ invalid onto functions.

• Subtract the invalid functions from the total onto functions: $30 - 10 = 20$ valid ways.

Alternatively, we can think of this as partitioning the $5$ remaining elements of $A$ into two sets of size $3$ and $2$.

• Ways to partition: $\binom{5}{3} = 10$.

• Ways to assign these partitions to the $2$ remaining elements in $B: 2! = 2$.

• $10 \times 2 = 20$ valid ways.

 

Therefore, the total number of onto functions is $ = 252 \times 20 = \boxed{\mathbf{5040}}$