Question

Let \( A = \{1, 2, 3, 4, 5\} \) and \( B = \{a, b, c\} \). Then the number of functions which are not onto are:

• A. 84
• B. 93
• C. 100
• D. 54

Hint:

The number of "not onto" functions is simply the sum of the terms we subtract in the inclusion-exclusion formula for onto functions. In this case, it is \( ^3C_1(2^5) - ^3C_2(1^5) = 93 \).

Answer 1

The Correct Option is B

To solve the problem of finding the number of functions from set \( A = \{1, 2, 3, 4, 5\} \) to set \( B = \{a, b, c\} \) that are not onto, we need to understand a few concepts about functions.

A function from set \( A \) to set \( B \) maps every element of \( A \) to exactly one element of \( B \). The number of such functions is given by \( |B|^{|A|} \), where \( |A| \) is the number of elements in \( A \) and \( |B| \) is the number of elements in \( B \).

Here, \( |A| = 5 \) and \( |B| = 3 \). Therefore, the total number of functions from \( A \) to \( B \) is:

\(3^5 = 243\)

An onto function, also called a surjective function, is one where every element in the codomain \( B \) is the image of at least one element from domain \( A \). We need to calculate how many functions are not onto.

To find this, we first calculate the number of onto functions using the formula involving the principle of inclusion-exclusion:

The formula for the number of onto functions is given by \( S(n,r) \times r! \), where \( S(n,r) \) is the Stirling number of the second kind, counting the number of ways to partition a set of \( n \) elements into \( r \) non-empty subsets.

We need \( S(5,3) \), so:

• Using the relation \( S(n, k) = k \times S(n-1, k) + S(n-1, k-1) \), we build the Stirling numbers:
• \( S(0,0) = 1 \), \( S(n,0) = 0 \) for \( n \geq 1 \), \( S(0,k) = 0 \) for \( k \geq 1 \).
• \( S(1,1) = 1 \), \( S(2,1) = 1 \), \( S(2,2) = 1 \)
• \( S(3,1) = 1 \), \( S(3,2) = 3 \), \( S(3,3) = 1 \)
• \( S(4,1) = 1 \), \( S(4,2) = 7 \), \( S(4,3) = 6 \)
• \( S(5,1) = 1 \), \( S(5,2) = 15 \), \( S(5,3) = 25 \)

So, the number of onto functions from \( A \) to \( B \) is \( S(5,3) \times 3! = 25 \times 6 = 150 \).

The number of functions which are not onto is the total number of functions minus the onto functions:

\(243 - 150 = 93\)

Therefore, the number of functions that are not onto is 93. This matches the correct answer option.