In this article, we are discussing how to find number of functions from one set to another. For understanding the basics of functions, you can refer this: Classes (Injective, surjective, Bijective) of Functions. Number of functions from one set to another: Let X and Y are two sets having m and n elements respectively. In a function from X to Y, every element of X must be mapped to an element of Y. Therefore, each element of X has ‘n’ elements to be chosen from. Therefore, total number of functions will be n×n×n.. m times = nm.
For example: X = {a, b, c} and Y = {4, 5}. A function from X to Y can be represented in Figure 1.
Considering all possibilities of mapping elements of X to elements of Y, the set of functions can be represented in Table 1. Examples: Let us discuss gate questions based on this:
- Q1. Let X, Y, Z be sets of sizes x, y and z respectively. Let W = X x Y. Let E be the set of all subsets of W. The number of functions from Z to E is:
(A) z2xy
(B) z x 2xy
(C) z2x + y
(D) 2xyz Solution: As W = X x Y is given, number of elements in W is xy. As E is the set of all subsets of W, number of elements in E is 2xy. The number of functions from Z (set of z elements) to E (set of 2xy elements) is 2xyz. So the correct option is (D)
- Q2. Let S denote the set of all functions f: {0,1}4 → {0,1}. Denote by N the number of functions from S to the set {0,1}. The value of Log2Log2N is ______.
(A) 12
(B) 13
(C) 15
(D) 16 Solution: As given in the question, S denotes the set of all functions f: {0, 1}4 → {0, 1}. The number of functions from {0,1}4 (16 elements) to {0, 1} (2 elements) are 216. Therefore, S has 216 elements. Also, given, N denotes the number of function from S(216 elements) to {0, 1}(2 elements). Therefore, N has 2216 elements. Calculating required value, Log2(Log2 (2216)) =Log216 = 16 Therefore, correct option is (D).
Number of onto functions from one set to another – In onto function from X to Y, all the elements of Y must be used. In the example of functions from X = {a, b, c} to Y = {4, 5}, F1 and F2 given in Table 1 are not onto. In F1, element 5 of set Y is unused and element 4 is unused in function F2. So, total numbers of onto functions from X to Y are 6 (F3 to F8).
- If X has m elements and Y has 2 elements, the number of onto functions will be 2m-2.
Explanation: From a set of m elements to a set of 2 elements, the total number of functions is 2m. Out of these functions, 2 functions are not onto (If all elements are mapped to 1st element of Y or all elements are mapped to 2nd element of Y). So, number of onto functions is 2m-2. Solution : For one-one function each preimage in set A must have distinct image in set B.
So, number of one-one functions from set A to B
= number of permutations of five objects (images) taken three (preimages) at a time
`=""^(5)P_(3)=5xx4xx3=60.`
For onto function each image must have pre-image.
Now consider three elements of set A as three distinct boxes and five elements of set B as five distinct objects.
Number of onto functions from set A to B
= number of ways five distinct objects can be distributed into three boxes so that no box remains empty
`=3^(5)-""^(3)C_(1)(3-1)^(5)+""^(3)C_(2)(3-2)^(5)`
`=243-96+3`
`=150` Solution : Let `A = {1,2,3,4}`
`B = {a,b)`
Here, total number of functions possible `= 2**2**2**2 = 2^4`. Here, `n(A) = 4 and n(B) = 2`.
So, when, `n(A) = q and n(B) = p`,
Then total number of functions possible `=p^q`. The cardinality of $B^A$ is the same if $A$ (resp. $B$) is replaced with a set containing the same number of elements as $A$ (resp. $B$). Set $b = |B$|. When $b \lt 2$ there is little that needs to be addressed, so we assume $b \ge 2$. Assume $|A| = n$. A well known result of elementary number theory states that if $a$ is a natural number and $0 \le a \lt b^n$ then it has one and only one base-$\text{b}$ representation, $$\tag 1 a = \sum_{k=0}^{n-1} x_k\, b^k \text{ with } 0 \le x_k \lt b$$ Associate to every $a$ in the initial integer interval $[0, b^n)$ the set of ordered pairs $$\tag 2 \{(k,x_k) \, | \, 0 \le k \lt n \text{ and the base-}b \text{ representation of } a \text{ is given by (1)}\}$$ This association is a bijective enumeration of $[0, b^n)$ onto the set of all functions
mapping $[0,n-1]$ to $[0,b-1]$. Since $[0, b^n)$ has $b^n$ elements, we know how to count all the functions from one finite set into another.
What is the total number of functions defined from A to B if n A 2 and NB 3?
Hence , the answer is 64.
What is the total number of functions that can be defined from the set 1.2 to the set 1 2 3?
Solution : The total number of functions that can be defined from the set {1,2} to the set {1,2,3} is `3^2=9`. ADVERTISEMENT.
How many Bijective functions can be defined from A to B if A |= N and B |= M?
Solution : The number of functions from A to B = m^(3).
How many total relations can be defined from the set A to B?
Counting relations. Since any subset of A × B is a relation from A to B, it follows that if A and B are finite sets then the number of relations from A to B is 2|A×B| = 2|A|·|B|. One way to see this is as the number of subsets of A × B.
|
