Let A be a set of n distinct elements. Then the total number of distinct functions from A to A is ..

Q: Why is an onto function from a finite set to itself always one-to-one?

This is a beautiful consequence of the Pigeonhole Principle. If you have $n$ items and $n$ containers, and you want to ensure every container has at least one item (onto), the only way to do this is to put exactly one item in each container. If you put two items in one container, you would have to leave another container empty, which violates the onto condition. Thus, it must be a bijection.

Q: What if the set sizes were different? Would the formula change?

Absolutely! If the domain has $m$ elements and the codomain has $n$ elements, the total number of functions is $n^m$. However, the number of onto functions becomes much more complex, involving Stirling numbers of the second kind, specifically $n! \times S(m, n)$. The case where $|Domain| = |Codomain|$ is a special, elegant simplification.

Q: Is there a difference between 'onto' and 'surjective'?

No, they are synonyms! 'Onto' is the intuitive, geometric way of describing the mapping, while 'surjective' is the formal mathematical term. Both mean that the range of the function is equal to the codomain.

Question

Let $A$ be a set of $n$ distinct elements. Then the total number of distinct functions from $A$ to $A$ is ......... and out of these ......... are onto functions.

Sigma Percentile · Accepted Answer

### Analyzing the Setup

We are exploring functions from a set $A$ to itself, where the cardinality of the set is $|A| = n$. Let the set be defined as $A = \{a_1, a_2, \dots, a_n\}$.

When we define a function $f: A 	o A$, we are establishing a rule that assigns each element in the domain to an element in the codomain. This is the fundamental building block of mapping theory.

### The Freedom of Choice: Total Functions

To determine the total number of functions, we consider each element in the domain as an independent agent. The first element, $a_1$, has $n$ possible choices in the codomain.

Since there are no restrictions, the second element, $a_2$, also has $n$ choices, regardless of where $a_1$ mapped. This independence holds for all $n$ elements in the domain.

By the Fundamental Principle of Counting, we multiply these choices together:
$$n 	imes n 	imes \dots 	imes n 	ext{ ($n$ times)} = n^n$$

Thus, the total number of possible functions from $A$ to $A$ is **$n^n$**.

### The Constraint of 'Onto'

Now, we introduce the constraint that the function must be 'onto', or surjective. This requires that every element in the codomain is covered by at least one arrow from the domain.

In a scenario where the domain and codomain have the same number of elements ($n$), this constraint is transformative. If every element in the codomain must be covered, we cannot allow two elements in the domain to map to the same element in the codomain.

If any two elements mapped to the same target, the Pigeonhole Principle dictates that at least one element in the codomain would be left empty. Therefore, an onto function from a finite set to itself must be a bijection, meaning it is both injective and surjective.

### The Countdown to Factorial

This constraint changes our counting strategy from independent choices to a restricted selection process. The first element, $a_1$, has $n$ choices.

The second element, $a_2$, is now restricted; it cannot map to the element chosen by $a_1$. Consequently, $a_2$ has $n-1$ choices.

The third element, $a_3$, must avoid both $a_1$ and $a_2$, leaving it with $n-2$ choices. This pattern continues until the final element has only $1$ choice remaining.

The total number of such bijections is given by the product:
$$n 	imes (n-1) 	imes (n-2) 	imes \dots 	imes 1 = n!$$

By adding the requirement that every element must be accounted for, we transition from the total freedom of **$n^n$** to the strict, orderly arrangement of **$n!$**. Keep this logic in your toolkit, as it is essential for solving complex combinatorial problems in your JEE journey.

Animated Solution for Mathematics - Functions: Let $A$ be a set of $n$ distinct elements. Then the total number of distinct functions from $A$ to $A$ is ......... and out of these ......... are onto functions.

Visualized Solution

Visualizing the Sets

The Rule of Functions

Counting Choices for the First Element

Counting Choices for the Second Element

Total Number of Functions

The Onto Condition

Counting Onto Functions - First Element

Counting Onto Functions - Second Element

Total Number of Onto Functions

The Sigma Insight: Classification of Functions

Analyzing the Setup

The Freedom of Choice

The Constraint of 'Onto'

The Countdown to Factorial

Similar Questions

Let $E = {1, 2, 3, 4}$ and $F = {1, 2}$ . Then the number of onto functions from $E$ to $F$ is

Let $S = {1, 2, 3, 4}$ . Then the number of elements in the set ${f : S \times S \to S : f is onto and f (a, b) = f (b, a) \geq a \forall (a, b) \in S \times S}$ is ______.

Consider two sets $A = {x \in Z : ∣ (∣ x - 3∣ - 3) ∣ \leq 1}$ and $B = {x \in R - {1, 2} : \frac{( x - 2 ) ( x - 4 )}{x - 1} lo g_{e} (∣ x - 2∣) = 0}$ . Then the number of onto functions $f : A \to B$ is equal to

Let $A = {1, 2, 3, 5, 8, 9}$ . Then the number of possible functions $f : A \to A$ such that $f (m \cdot n) = f (m) \cdot f (n)$ for every $m, n \in A$ with $m \cdot n \in A$ is equal to

Let $A = {a, b, c}$ and $B = {1, 2, 3, 4}$ . Then the number of elements in the set $C = {f : A \to B ∣2 \in f (A) and f is not one-one}$ is

The number of one-one function $f : {a, b, c, d} \to {0, 1, 2, \dots, 10}$ such that $2 f (a) - f (b) + 3 f (c) + f (d) = 0$ is ______.

Let $A = {0, 1, 2, 3, 4, 5, 6, 7}$ . Then the number of bijective functions $f : A \to A$ such that $f (1) + f (2) = 3 - f (3)$ is equal to

Let $S = {1, 2, 3, 4, 5, 6, 7}$ . Then the number of possible functions $f : S \to S$ such that $f (m \cdot n) = f (m) \cdot f (n)$ for every $m, n \in S$ and $m \cdot n \in S$ is equal to

Let $x$ denote the total number of one-one functions from a set $A$ with 3 elements to a set $B$ with 5 elements and $y$ denote the total number of one-one functions from the set $A$ to the set $A \times B$ . Then:

Let $A = {1, 2, 3, 4}$ and $B = {1, 4, 9, 16}$ . Then the number of many-one functions $f : A \to B$ such that $1 \in f (A)$ is equal to: