Question

Consider two sets A = {2, 3, 5, 7, 11, 13} and B = {1, 8, 27}. Let f be a function from A to B such that for every element b in B, there is at least one element a in A such that f(a) = b. Then, the total number of such functions f is

• A. 537
• B. 540
• C. 667
• D. 665

Answer 1

The Correct Option is B

To determine the total number of functions \( f: A \to B \) such that for every element \( b \) in \( B \), there is at least one element \( a \) in \( A \) with \( f(a) = b \), we need to ensure that the function \( f \) is onto (surjective).

Given: 

• Set A = {2, 3, 5, 7, 11, 13} with 6 elements.
• Set B = {1, 8, 27} with 3 elements.

Since \( A \) has 6 elements and \( B \) has 3 elements, we need to find the number of surjective functions from 6 elements to 3 elements.

The number of surjective functions from a set with \( m \) elements to a set with \( n \) elements is given by the formula:

\[ n! \times \left\{ \!\! \begin{array}{c} m \\ n \end{array} \!\! \right\} \]

 

where \(\left\{ \!\! \begin{array}{c} m \\ n \end{array} \!\! \right\}\) denotes the Stirling number of the second kind, representing the number of ways to partition a set of \( m \) elements into \( n \) non-empty subsets.

Applying this to our problem:

(i) Calculate \( 3! \):

\[ 3! = 3 \times 2 \times 1 = 6 \]

 

(ii) Calculate the Stirling number of the second kind \( \left\{ \!\! \begin{array}{c} 6 \\ 3 \end{array} \!\! \right\} \):

Using known values, \(\left\{ \!\! \begin{array}{c} 6 \\ 3 \end{array} \!\! \right\} = 90\).

(iii) Calculate the total number of surjective functions:

\[ 3! \times \left\{ \!\! \begin{array}{c} 6 \\ 3 \end{array} \!\! \right\} = 6 \times 90 = 540 \]

 

Thus, the total number of surjective functions \( f \) is 540.

Answer 2

Each element of set $B$ must be mapped to at least one element of set $A$, and we need to count how many such functions are possible.

We have 6 elements in set $A$ and 3 elements in set $B$. The condition is that each element in $B$ must have at least one pre-image in $A$, so we are looking for surjections (onto functions).

The total number of surjections from a set of size 6 to a set of size 3 can be calculated using the inclusion-exclusion principle.

The number of surjections from a set of size 6 to a set of size 3 is given by:

$3^6 - \binom{3}{1} 2^6 + \binom{3}{2} 1^6 = 729 - 192 + 3 = 540$

Thus, the total number of such functions is 540.