How many one to one functions are there from a set with m elements to one with n elements

Hint: For solving this problem, we first find the number of elements given for set A. The number of one-one functions from A to B is 5040. Let the number of elements in B be n. Now by applying the formula for one-one functions that is ${}^{n}{{P}_{m}}$, we can obtain the number of elements in B.

Complete step-by-step solution -
A function as is said to be a one-one function or an injection, if different elements of A have different images in B. If A and B are finite sets having m and n elements respectively such that m is less than equal to n, then to define a one-one function from A to B, we have to relate m elements in A to n distinct elements in B. Thus, number of one-one function: ${}^{n}{{P}_{m}}$.
According to our problem we are given that the number of functions that can be defined from A to B is 5040. The number of elements in A are 4. We are required to find the number of elements in B. By using the above formula and putting m = 4 and n same, we get
$ \Rightarrow {}^{n}{{P}_{m}}=5040 \\ $
$ \Rightarrow {}^{n}{{P}_{4}}=5040 \\ $
From the definition of permutation, ${}^{n}{{P}_{r}}=\dfrac{n!}{\left( n-r \right)!}$
On expanding further, we get
$\Rightarrow {}^{n}{{P}_{4}}=\dfrac{n!}{\left( n-4 \right)!} \\ $
$\Rightarrow \dfrac{n!}{\left( n-4 \right)!}=5040 \\ $
As, we know $\ {}^{10}{{P}_{4}}=5040 \\ $
$\Rightarrow \dfrac{n!}{\left( n-4 \right)!}=\dfrac{10!}{\left( 10-4 \right)!} \\ $
$ \therefore n=10 \\ $
Therefore, there are 10 elements present in B.
Hence, option (d) is correct.

Note: Another possible method to solve this problem can be explained as: Let the first element 4 in A be mapped on n elements of B. Similarly, the second element 8 is mapped on (n -1) elements. Hence, we can write for four elements mapping as: $n\left( n-1 \right)\left( n-2 \right)\left( n-3 \right)=5040$. Putting n as 10, we get the same result.

Hint: Use the cardinality of two sets to find the number of one-one functions between them.
\[\text{Number of one-one functions = }{}^{n}{{P}_{m}}\text{ if n}\ge \text{m}\]…..(1)
Number of one-one functions = 0 if n < m…..(2)

Complete step-by-step answer:
The total number of elements in the set is called the cardinality of the set.
Let us assume given sets as A and B, that is,
A = {a, b, c, d} and B = {1, 2, 3, 4}
The cardinality of a set is denoted by “|set|”
Here cardinality of A = |A| = 4.
Cardinality of B = |B| = 4.
If there are two non-empty sets with cardinality m and n, then the number of one-one functions between them is given by:
\[\text{Number of one-one functions = }{}^{n}{{P}_{m}}\text{ if n}\ge \text{m}\] …..(1)
Number of one-one functions = 0 if n < m…..(2)
By the above formula, in our case the value of m is 4 and the value of n is 4.
We can see that m = n.
So we need to use equation (1):
\[\text{Number of one-one functions = }{}^{n}{{P}_{m}}\text{ if n}\ge \text{m}\].
So, the number of one-one functions = \[{}^{4}{{P}_{4}}\]
By using the formula,
\[{}^{n}{{P}_{m}}=\dfrac{n!}{\left( n-m \right)!}\]
By substituting factorial of 0 as 1,we get:
\[\text{The number of one-one functions }={}^{4}{{P}_{4}}=\dfrac{4!}{(4-4)!}=4!\] [$\because$ 0!=1]

The number of one-one functions = (4)(3)(2)(1) = 24.
\[\therefore \]The total number of one-one functions from {a, b, c, d} to {1, 2, 3, 4} is 24.

Note: Here the values of m, n are same but in case they are different then the direction of checking matters. If m > n, then the number of one-one from first set to the second becomes 0. So take care of the direction of checking.

Number of functions is an important topic in sets. A relation in which each input has a particular output is called a function. If f is a function from set A to set B, then each element of A will be mapped with only one element in B. In this article, we come across the formula to find the number of functions from given sets and some solved examples.

Consider a set X having 6 elements and another set Y having 5 elements. Every element of set X will be mapped to one element in set Y. So each element of X has 5 elements to be chosen from. Hence, the total number of functions will be 5×5×5.. 6 times = 56.

Formula For Number Of Functions

1. Number of possible functions

If a set A has m elements and set B has n elements, then the number of functions possible from A to B is nm.

For example, if set A = {3, 4, 5}, B = {a, b}.

The total number of possible functions from A to B = 23 = 8

2. Number of Surjective Functions (Onto Functions)

If a set A has m elements and set B has n elements, then the number of onto functions from A to B = nm – nC1(n-1)m + nC2(n-2)m – nC3(n-3)m+….- nCn-1 (1)m.

Note that this formula is used only if m is greater than or equal to n.

For example, in the case of onto function from A to B, all the elements of B should be used. If A has m elements and B has 2 elements, then the number of onto functions is 2m-2. From a set A of m elements to a set B of 2 elements, the total number of functions is 2m. In these functions, 2 functions are not onto (If all elements are mapped to 1st element of B or all elements are mapped to 2nd element of B). So, the number of onto functions is 2m-2.

3. Number of Injective Functions (One to One)

If set A has n elements and set B has m elements, m≥n, then the number of injective functions or one to one function is given by m!/(m-n)!.

4. Number of Bijective functions

If there is bijection between two sets A and B, then both sets will have the same number of elements. If n(A) = n(B) = m, then number of bijective functions = m!.

Solved Examples – Number Of Functions

Example 1:

The number of onto functions from set P = {a, b, c, d} to set Q = {u, v, w} is:

(A) 68

(B) 36

(C) 81

(D) 64

Solution:

P = {a, b, c, d}

Q = {u, v, w}

Here n(P) = m = 4

n(Q) = n = 3

The number of onto functions = 34 – 3C1(3-1)4 + 3C2(3-2)4

= 81 – 48 + 3

= 36.

Hence, option B is the answer.

Example 2:

The number of bijective functions from set A to itself when A contains 106 elements is

(A) 106

(B) 106!

(C) 1062

(D) 2106

Solution:

n(A) = m = 106

The number of bijective functions = m!

= 106!

Hence, option B is the answer.

Related video

Frequently Asked Questions

How do you find the number of functions?

Let set A has p elements and set B has q elements, then the number of functions possible from A to B is qp.

How do you calculate the number of injective functions?

If n(A) = n and n(B) = m, m≥n, then the number of injective functions or one to one functions is given by m!/(m-n)!.

How do you calculate the number of bijective functions?

If n(A) = n(B) = p, then the number of bijective functions = p!.

What do you mean by one to one function?

A function is one-to-one if every element of the range of the function corresponds to exactly one element of the domain of the function.

How many onto functions are there from a set with m elements to one with N elements?

So, the number of onto functions is 2^m-2. If set A has n elements and set B has m elements, m≥n, then the number of injective functions or one to one function is given by m!/(m-n)!.

How many functions does a set with N elements have?

Therefore, number of functions that can be defined from A into A =n(A)n(A)=nn.

How many one

The number of one to one functions is N!, because the max mapping to Y is N.

How many one one functions can be defined?

nPm=n! (n−m)! By substituting factorial of 0 as 1,we get: The number of one-one functions =4P4=4!