SOLVER7 Study. Nothing Else.
Miscellaneous Exercise Chapter 1 Q4

Find the number of all onto functions from the set \(\{1, 2, 3,......, _n\}\) to itself.

CBSE Class 12 Maths · Relations and Functions

Solution

👶 Simple Explanation

Simple Explanation

Imagine you have chairs numbered 1 to n and the same number of children. An onto function means every chair must be occupied by at least one child. Since there are equal chairs and children, every chair gets exactly one child. This is like arranging children in chairs — no empty chairs allowed. The number of ways to arrange n children in n chairs is \( n! \), meaning n choices for the first chair, then n minus 1 for the next, and so on multiplied together.

Answer: The number of all onto functions from \( \{1, 2, 3, \ldots, n\} \) to itself is \( n! \).

📖 Number of Onto Functions from a Finite Set to Itself

Detailed Explanation

A function \( f: A \to A \) is called onto (surjective) if every element of the codomain has at least one pre-image in the domain. Here the domain and codomain are the SAME finite set \( A = \{1, 2, 3, \ldots, n\} \), which has exactly \( n \) elements. A very important result for finite sets holds: when a function maps a finite set to itself (equal number of elements in domain and codomain), the function is onto if and only if it is one-one. In other words, for such sets, onto, one-one, and bijective all mean the same thing. So counting onto functions is the same as counting bijective functions (one-one and onto), and a bijection from a set to itself is simply an arrangement (permutation) of its \( n \) elements.

Formula Used

Number of onto functions from a set with \( n \) elements to itself \( = n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 \)

Solution

  1. Step 1: Note that the domain and codomain are the same set \( A = \{1, 2, 3, \ldots, n\} \), which has exactly \( n \) elements. So we are counting functions from an \( n \)-element set to itself.
  2. Step 2: Use the key result for finite sets: if a function maps a finite set to itself, then it is onto if and only if it is one-one. Therefore every onto function here must also be one-one, i.e. it is a bijection. So counting onto functions is exactly the same as counting bijections (one-one and onto functions).
  3. Step 3: Count the bijections. A bijection assigns to each element a distinct image, with no repetition. Consider assigning images one element at a time. The element \( 1 \) can be sent to any of the \( n \) elements, so there are \( n \) choices.
  4. Step 4: Since images must be distinct, the element \( 2 \) can be sent to any of the remaining \( n-1 \) elements. Similarly, the element \( 3 \) has \( n-2 \) choices, and so on, until the last element has only \( 1 \) choice left.
  5. Step 5: By the multiplication principle, the total number of such bijections is the product of all these choices: \[ n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 = n! \]

Final Answer

The number of all onto functions from \( \{1, 2, 3, \ldots, n\} \) to itself is \( n! \).

Common Mistake

A common mistake is to count total functions \( n^n \) instead of onto functions. That counts every mapping (allowing repeated images), but onto functions to the same set must use every image exactly once, giving \( n! \), not \( n^n \).

🪜 Step-by-step Solution

Step-by-step Solution

  1. Step 1: Identify the sets involved: both the domain and the codomain are the same set \( A = \{1, 2, 3, \ldots, n\} \), which contains exactly \( n \) elements. — Reason: Recognising that domain and codomain are identical and finite is the key starting point, because this equality in size has a powerful consequence for onto functions.
  2. Step 2: Recall the definition of an onto function: \( f: A \to A \) is onto if every element of the codomain \( A \) has at least one pre-image in the domain \( A \). — Reason: Grounding ourselves in the definition helps us understand exactly what condition must be satisfied by every function we count.
  3. Step 3: Apply the key theorem for finite sets: if a function maps a finite set to itself (same number of elements in domain and codomain), then the function is onto if and only if it is also one-one. In other words, for \( f: A \to A \) with \( |A| = n \), onto \( \Leftrightarrow \) one-one \( \Leftrightarrow \) bijective. — Reason: Because the domain and codomain have the same finite size \( n \), there is no room for any element to be left without a pre-image unless some element is repeated, which would violate the one-one condition.
  4. Step 4: Conclude that counting onto functions is exactly the same as counting bijections (one-one and onto functions) from \( A \) to itself. A bijection from a set to itself is precisely a permutation of its elements. — Reason: Since onto and bijective are equivalent here, we only need to count permutations, which is a standard combinatorics result.
  5. Step 5: Count the total number of permutations of \( n \) elements: the first element of the domain can be mapped to any of \( n \) choices, the second to any of the remaining \( n - 1 \) choices, and so on down to the last element which has exactly \( 1 \) choice. By the multiplication principle, the total count is \[ n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 = n! \] — Reason: Each successive assignment reduces the available images by one (to keep the function one-one), so we multiply the choices at each stage.
  6. Step 6: State the final result: the number of onto functions from \( \{1, 2, 3, \ldots, n\} \) to itself equals \( n! \). — Reason: We have shown the equivalence with permutations and computed the permutation count, so the answer follows directly.

Final Answer

The number of all onto functions from \( \{1, 2, 3, \ldots, n\} \) to itself is \( n! \).

Common Mistake

One common mistake: students apply the general formula for onto functions from an \( m \)-element set to an \( n \)-element set (involving inclusion-exclusion) even when the domain and codomain are the same finite set, instead of recognising that onto automatically implies bijective in this special case, giving the much simpler answer \( n! \).

✍️ Exam-ready Answer

Exam-ready Answer

  1. Step 1: Domain = Codomain = \( \{1, 2, 3, \ldots, n\} \), a finite set with \( n \) elements.
  2. Step 2: For a finite set mapped to itself: onto \( \Leftrightarrow \) one-one \( \Leftrightarrow \) bijection.
  3. Step 3: Number of bijections = number of permutations of \( n \) elements \( = n! \).

Answer: The number of all onto functions from \( \{1, 2, 3, \ldots, n\} \) to itself is \( n! \).

➕ More Examples

More Examples

Example 1

Question: Find the number of all onto functions from the set \( A = \{a, b, c, d, e\} \) to itself.

Solution: The set \( A \) has \( n = 5 \) elements. We need to count all onto (surjective) functions from \( A \) to \( A \). Since the domain and codomain are the same finite set with \( n = 5 \) elements, a function \( f: A \to A \) is onto if and only if it is one-one (injective). This is because for finite sets of equal size, injectivity and surjectivity are equivalent. A one-one and onto function is a bijection, which corresponds to a permutation of the elements of \( A \). The total number of permutations of 5 elements is \( 5! \). Calculating: \[ 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120 \] Therefore, the number of onto functions from \( A \) to itself is \( 120 \).

Answer: 120

Example 2

Question: A class teacher wants to assign each of 7 distinct tasks to 7 distinct students such that every student gets exactly one task and every task is assigned. In how many ways can this assignment be done? Express your answer in terms of the number of onto functions from a 7-element set to itself.

Solution: Let the set of 7 students be \( S = \{s_1, s_2, s_3, s_4, s_5, s_6, s_7\} \) and the set of 7 tasks be \( T = \{t_1, t_2, t_3, t_4, t_5, t_6, t_7\} \). Since both sets have \( n = 7 \) elements, this assignment is equivalent to finding the number of onto functions from a 7-element set to itself. For any finite set of \( n \) elements, the number of onto functions from the set to itself equals the number of bijections (permutations), because on a finite set of equal size, a function is onto if and only if it is one-one. The number of bijections (permutations) of 7 elements is \( 7! \). Calculating step by step: \[ 7! = 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 \] First: \( 7 \times 6 = 42 \), then \( 42 \times 5 = 210 \), then \( 210 \times 4 = 840 \), then \( 840 \times 3 = 2520 \), then \( 2520 \times 2 = 5040 \), then \( 5040 \times 1 = 5040 \). So: \[ 7! = 5040 \] The number of onto functions from a 7-element set to itself, and hence the number of valid assignment schemes, is \( 5040 \).

Answer: 5040

🎯 Try a Similar Question

Try a Similar Question

Question: Let \( A = \{a, b, c, d, e\} \) be a set with 5 elements. Find the number of all onto functions from \( A \) to itself. Also, verify that every such onto function must necessarily be one-one.

Solution

  1. Step 1: Understand the condition for an onto function on a finite set: A function \( f : A \to A \) is onto (surjective) if every element of \( A \) appears in the range of \( f \). Here \( |A| = 5 \), so the domain and codomain both have 5 elements.
  2. Step 2: Show that onto implies one-one for equal finite sets: Suppose \( f : A \to A \) is onto but NOT one-one. Then at least two distinct elements map to the same image, meaning at most 4 distinct images are produced. But \( |A| = 5 \), so the range can have at most 4 elements, which means \( f \) cannot cover all 5 elements of \( A \). This contradicts the assumption that \( f \) is onto. Hence every onto function from \( A \) to itself must be one-one, i.e., it must be a bijection.
  3. Step 3: Count the number of bijections: A bijection from \( A \) to \( A \) is simply a permutation of the 5 elements \( \{a, b, c, d, e\} \). The first element can be mapped to any of the 5 elements, the second to any of the remaining 4, and so on. Therefore the total number of such bijections is \[ 5 \times 4 \times 3 \times 2 \times 1 = 5! \]
  4. Step 4: Compute the value: Evaluating the factorial: \[ 5! = 120 \] So there are 120 onto functions from \( A \) to itself.

Answer: The number of all onto functions from \( A = \{a, b, c, d, e\} \) to itself is \( 5! = 120 \). Every such onto function is also one-one (a bijection).

Everything you get with Solver7

More questions in Relations and Functions