Number of injective, surjective, bijective functions.

Question

In the text of Discrete Mathl. Structures'by 'Tremblay', in Exercise 2-4.3, there is Q.#4 as given below. Request vetting.:

Find number of each type of function (injective, surjective, bijective) from below:
(i) $X =\{1,2,3\}\,\, \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,Y = \{1,2,3\}$
(ii) $X =\{1,2,3,4\} \,\, \,\,\,\,\,\,\,\,\,\, Y = \{1,2,3\}$
(iii) $X =\{1,2,3\} \,\, \,\,\,\,\,\,\,\,\,\,\,\,\, Y = \{1,2,3,4\}$

The total number of functions, & functions are given below:
(i) Total of $3^3=27$ functions, with set of $9$ ordered pairs listed below, with 2nd & 3rd elements of the sets having the first ordered pair as $<2,i>$ & $<3,i>$, s.t. $\,\,\,i\in \{1,2,3\}$

$f_0 = \{<1,1>, <2,1>, <3,1>\}$
$f_1 = \{<1,1>, <2,2>, <3,2>\}$
$f_2 = \{<1,1>, <2,3>, <3,3>\}$
$f_3 = \{<1,1>, <2,1>, <3,2>\}$
$f_4 = \{<1,1>, <2,2>, <3,1>\}$
$f_5 = \{<1,1>, <2,1>, <3,3>\}$
$f_6 = \{<1,1>, <2,3>, <3,1>\}$
$f_7 = \{<1,1>, <2,2>, <3,3>\}$
$f_8 = \{<1,1>, <2,3>, <3,2>\}$

In the above set -

• the number of one-to-one functions are :$\,\,2$, i.e. $f_7, f_8$ ;
  
• number of onto functions are :$\,\,2$, which are the same functions as earlier
  $\,\,\,$ (is expected as has a finite set of domain & range)
  
• the number of bijective functions is the same $=2$.

So, the total number of one-to-one & onto functions are :$\,\,2*3 = 6$; & all the same functions.

---

(ii) Total of $3^4=81$ functions, by multiplication principle as each range member can have any of the domain member.
There will be groups based on number of range members, i.e. $3$ groups of $27$ ordered pairs. The ordered pairs, even though have first member as of domain, is limited by the number of range member to which it can map.
The first group of $27$ ordered pairs with ordered pairs starting with $<1,1>$ are listed below. The other $27*2=54$ ordered pairs are found similar to in part (i):
$f_0 = \{<1,1>, <2,1>, <3,1>, <4,1>\}$
$f_1 = \{<1,1>, <2,2>, <3,2>, <4,1>\}$
$f_2 = \{<1,1>, <2,3>, <3,3>, <4,1>\}$
$f_3 = \{<1,1>, <2,1>, <3,2>, <4,1>\}$
$f_4 = \{<1,1>, <2,2>, <3,1>, <4,1>\}$
$f_5 = \{<1,1>, <2,1>, <3,3>, <4,1>\}$
$f_6 = \{<1,1>, <2,3>, <3,1>, <4,1>\}$
$f_7 = \{<1,1>, <2,2>, <3,3>, <4,1>\}$
$f_8 = \{<1,1>, <2,3>, <3,2>, <4,1>\}$
The other $18$ elements of the first group are obtained by having the last ordered pair as : $<4,2>$ and $<4,3>$ with each contributing $9$ ordered pairs.

There will be no function that is one-to-one, but the number of onto functions will be $2*3$ in each group of $27$, hence $2*3*3= 18$ in total. Say, in the above group of $9$ members the onto functions are: $f_7, f_8$; & for the rest of $18$ functions in the first group there are$4$ more such functions. There would be no bijective functions.

---

(iii) Total of $4^3=64$ functions, by multiplication principle as each range member can have any of the domain member.
There will be groups based on number of range members, i.e. $4$ groups of $16$ functions (set of ordered pairs).
The first group of $16$ ordered pairs with ordered pairs starting with $<1,1>$ are listed below. The other $16*2=32$ ordered pairs are found similarly.
$f_0 = \{<1,1>, <2,1>, <3,1>\}$
$f_1 = \{<1,1>, <2,1>, <3,2>\}$
$f_2 = \{<1,1>, <2,1>, <3,3>\}$
$f_3 = \{<1,1>, <2,1>, <3,4>\}$
$f_4 = \{<1,1>, <2,2>, <3,1>\}$
$f_5 = \{<1,1>, <2,2>, <3,2>\}$
$f_6 = \{<1,1>, <2,2>, <3,3>\}$
$f_7 = \{<1,1>, <2,2>, <3,4>\}$
$f_8 = \{<1,1>, <2,3>, <3,1>\}$
$f_9 = \{<1,1>, <2,3>, <3,2>\}$
$f_{10} = \{<1,1>, <2,3>, <3,3>\}$
$f_{11} = \{<1,1>, <2,3>, <3,4>\}$
$f_{12} = \{<1,1>, <2,4>, <3,1>\}$
$f_{13} = \{<1,1>, <2,4>, <3,2>\}$
$f_{14} = \{<1,1>, <2,4>, <3,3>\}$
$f_{15} = \{<1,1>, <2,4>, <3,4>\}$
In the above group of $16$ functions, there are $6$ one-to-one functions: $f_6, f_7, f_9, f_{11}, f_{13}, f_{14}$. So, a total of $18$ one-to-one functions.

---

Update - It seems there should be a way to tell the no. of injective, surjective functions based on number of elements in domain & range. If $|D|, |R|$ be the number of elements in the domain & range; then there should be some sort of formula to get the number of injective, surjective functions, whichever is possible.

Answer 1

Find the number of functions $f: X \to Y$, where $X = Y = \{1, 2, 3\}$, that are

(a) injective

(b) surjective

(c) bijective

You are correct that there are $3! = 6$ functions that are injective, bijective, and surjective.

For the injective functions, there are three ways to choose $f(1)$, two ways to choose $f(2)$ since it must differ from $f(1)$, and one way to choose $f(3)$ since it must differ from both $f(1)$ and $f(2)$. Hence, there are $3! = 6$ injective functions.

For the surjective functions, each of the three elements in the codomain must be in the range. Since there are three elements in the domain, each element in the domain must be mapped to a different element in the codomain. That is, it must be an injective function. Since every injective function $f: X \to Y$ is also surjective, there are $3! = 6$ surjective functions.

Since each of these $3!$ functions are injective and surjective, they are bijective. Hence, there are $3! = 6$ bijective functions $f: X \to Y$.

Another way to count the surjective functions:

There are $3^3$ functions $f: X \to Y$. From these, we must subtract those functions that have fewer than three elements in their ranges.

There are $\binom{3}{1}$ ways to exclude one element in the codomain from the range and $2^3$ ways to map the three elements in the domain the the remaining elements in the codomain. Hence, there are $\binom{3}{1}2^3$ functions $f: X \to Y$ that exclude one element in the codomain from the range.

However, if we subtract those functions that exclude one element from their range, we will have subtracted too much since we will have subtracted functions that exclude two elements from their range twice, once for each of the two ways we could have excluded one of the other two elements in the codomain from the range. Hence, we must add them back.

There are three such functions, namely the three constant functions.

It is not possible to exclude all three elements in the codomain from the range.

Hence, by the Inclusion-Exclusion Principle, the number of surjective functions is $$3^3 - \binom{3}{1}2^3 + \binom{3}{2}1^3 = 27 - 24 + 3 = 6$$ Hence, we have the identity $$\sum_{i = 0}^{3} (-1)^i\binom{3}{i}(3 - i)^3 = 3!$$ In general, if $n$ is finite, $$\sum_{i = 0}^{n} (-1)^i\binom{n}{i}(n - i)^n = n!$$ The left-hand side counts the number of surjective functions from a set with $n$ elements to a set with $n$ elements. The right-hand side counts the number of injective functions from a set with $n$ elements to a set with $n$ elements. Since every injective function from a set with $n$ elements to a set with $n$ elements is surjective and every surjective function from a set with $n$ elements is injective, the number of bijective functions from a set with $n$ elements is $n!$.

Find the number of functions $f: X \to Y$, where $X = \{1, 2, 3, 4\}$ and $Y = \{1, 2, 3\}$ that are

(a) injective

(b) surjective

(c) bijective

By the Pigeonhole Principle if we map a set with four elements to a set with three elements, at least two of the elements in the domain must be mapped to the same element of the range. Therefore, there are no injective functions $f: X \to Y$.

There are $3^4$ functions from $X$ to $Y$.

There are $\binom{3}{1}$ ways to exclude one element from the range and $2^4$ ways to map the elements in the domain to the remaining two elements in the domain, giving $\binom{3}{1}2^4$ functions $f: X \to Y$ that exclude one element of the codomain from their range.

However, if we subtract those functions that exclude one element in the codomain from their range, we will have subtracted too much since we will have subtracted those functions that exclude two elements from the codomain from their range twice, once for each way we could have designated one of the excluded elements as the excluded element. Since we only want to exclude such functions once, we must add them back.

There are $\binom{3}{2}$ ways to exclude two elements from the range and $1^4$ ways to assign the elements in the domain to the remaining element in the codomain. Thus, there are $\binom{3}{2}1^4$ ways to exclude two elements of the codomain from the range.

It is not possible to exclude all three elements of the codomain from the range.

By the Inclusion-Exclusion Principle, there are $$\sum_{i = 0}^{3} (-1)^i\binom{3}{i}(3 - i)^4 = 3^4 - \binom{3}{1}2^4 + \binom{3}{2}1^4 - \binom{3}{3}0^4 = 81 - 48 + 3 - 0 = 36$$ surjective functions $f: X \to Y$.

In general, the number of surjective functions $f: X \to Y$ if $|X| = k$ and $|Y| = n$ is $$\sum_{i = 0}^{k} (-1)^i\binom{n}{i}(n - i)^n$$ Alternatively, note that any surjective function must map two elements of the domain to one of the three elements in the codomain and the remaining elements in the domain must be mapped to different elements among the remaining two elements in the codomain. There are $\binom{4}{2}$ ways to select which two elements of the domain are mapped to the same element in the codomain, three ways to choose that element of the codomain, and $2!$ ways to assign the remaining two elements in the domain to different elements among the remaining two elements of the codomain. Hence, there are $$\binom{4}{2}3! = 36$$ surjective functions $f: X \to Y$.

Since any bijective function $f: X \to Y$ must be injective, there are no bijective functions $f: X \to Y$.

Find the number of functions $f: X \to Y$, where $X = \{1, 2, 3\}$ and $Y = \{1, 2, 3, 4\}$ that are

(a) injective

(b) surjective

(c) bijective

If $f: X \to Y$, there are four ways to assign $f(1)$, three ways to assign $f(2)$ to a different element in the codomain from $f(1)$, and two ways to assign $f(3)$ to a different element in the codomain from $f(1)$ and $f(2)$. Hence, there are $$P(4, 3) = 4 \cdot 3 \cdot 2 = 24$$ injective functions $f:X \to Y$. In general, there are $P(n, k)$ injective functions $f: X \to Y$ if $|X| = k$ and $|Y| = n$.

Since the three elements in the domain can be mapped to at most three of the four elements in the codomain, there are no surjective functions $f: X \to Y$.

Since any bijective function $f: X \to Y$ must be surjective, there are no bijective functions $f: X \to Y$.

Answer 2

In the case $X=Y=\{1,2,3\}$ injective and surjective functions are the same. They're $3!$: three choices where to map $1$, two where to map $2$ and the value at $3$ is so determined.

Similarly for $X=\{1,2,3\}$ and $Y=\{1,2,3,4\}$; for an injective map you have four choices where to map $1$, three for $2$ and two for $3$. Thus $4\cdot 3\cdot 2=24$. No map can be surjective.

The most interesting case is $X=\{1,2,3,4\}$ and $Y=\{1,2,3\}$. No map can be injective. Let's count the surjective ones. A map $f\colon X\to Y$ partitions $X$ into subsets, where in each subset we gather those elements of $X$ having the same image. Since we want that $f$ is surjective, the partition should consist of three subsets. Conversely, each partition into three subsets defines $3!$ surjective maps (exactly by the same argument in the first case above.

A partition into three subsets must have the form $\{\{\bullet,\bullet\},\{\bullet\},\{\bullet\}\}$ (substituting each $\bullet$ with distinct elements in $X$). In order to count them we have just to decide the two elements that should go together, which can be done in $$ \binom{4}{2}=\frac{4\cdot 3}{2\cdot 1}=6 $$ ways, because the order doesn't count; for instance, the choices {1,2}$ and ${2,1}$ should be counted as one.

Thus the total number of surjections is $$ \binom{4}{2}\cdot 3!=36 $$