Counting Functions

Total Number of Functions

Suppose $$A$$ and $$B$$ are finite sets with cardinalities $$\left| A \right| = n$$ and $$\left| B \right| = m.$$ How many functions $$f: A \to B$$ are there?

Recall that a function $$f: A \to B$$ is a binary relation $$f \subseteq A \times B$$ satisfying the following properties:

• Each element $$x \in A$$ is mapped to some element $$y \in B.$$
• Each element $$x \in A$$ is mapped to exactly one element $$y \in B.$$

The element $$x_1 \in A$$ can be mapped to any of the $$m$$ elements from the set $$B.$$ The same is true for all other elements in $$A,$$ that is, each of the $$n$$ elements in $$A$$ has $$m$$ choices to be mapped to $$B.$$ Hence, the number of distinct functions from $$f : A \to B$$ is given by

${m^n} = {\left| B \right|^{\left| A \right|}}.$

Counting Injective Functions

We suppose again that $$\left| A \right| = n$$ and $$\left| B \right| = m.$$ Obviously, $$m \ge n.$$ Otherwise, injection from $$A$$ to $$B$$ does not exist.

If we take the first element $$x_1$$ in $$A,$$ it can be mapped to any element in $$B.$$ So there are $$m$$ ways to map the element $$x_1.$$ For the next element $$x_2,$$ there are $$m-1$$ possibilities because one element in $$B$$ was already mapped to $$x_1.$$ Continuing this process, we find that the $$n\text{th}$$ element has $$m-n+1$$ options. Therefore, the number of injective functions is expressed by the formula

${m\left( {m – 1} \right)\left( {m – 2} \right) \cdots }\kern0pt{\left( {m – n + 1} \right) }={ \frac{{m!}}{{\left( {m – n} \right)!}}}$

Counting Surjective Functions

Let $$\left| A \right| = n$$ and $$\left| B \right| = m.$$ Now we suppose that $$n \ge m.$$ By definition of a surjective function, each element $$b_i \in B$$ has one or more preimages in the domain $$A.$$

Let $${f^{ – 1}}\left( {{y_i}} \right)$$ denote the set of all preimages in $$A$$ which are mapped to the element $$y_i$$ in the codomain $$B$$ under the function $$f.$$ The subsets $${f^{ – 1}}\left( {{y_1}} \right),{f^{ – 1}}\left( {{y_2}} \right), \ldots ,{f^{ – 1}}\left( {{y_m}} \right)$$ of the domain $$A$$ are disjoint and cover all elements of $$A.$$ Hence, they form a partition of the set $$A.$$ There are $$m$$ parts of the partition and they are bijectively mapped to the elements $$y$$ of the set $$B.$$

The number of partitions of a set of $$n$$ elements into $$m$$ parts is defined by the Stirling numbers of the second kind $$S\left( {n,m} \right).$$ Note that each element $$y_j \in B$$ can be associated with any of the parts. Therefore each partition produces $$m!$$ surjections.

Thus, the total number of surjective functions $$f : A \to B$$ is given by

$m!\,S\left( {n,m} \right),$

where $$\left| A \right| = n,$$ $$\left| B \right| = m.$$

Counting Bijective Functions

If there is a bijection between two finite sets $$A$$ and $$B,$$ then the two sets have the same number of elements, that is, $$\left| A \right| = \left| B \right| = n.$$

The number of bijective functions between the sets is equal to $$n!$$

Solved Problems

Click or tap a problem to see the solution.

Example 1

Let $$A = \left\{ {a,b,c,d} \right\}$$ and $$B = \left\{ {1,2,3,4,5} \right\}.$$ Determine:
1. the number of functions from $$A$$ to $$B.$$
2. the number of functions from $$B$$ to $$A.$$
3. the number of injective functions from $$A$$ to $$B.$$
4. the number of injective functions from $$B$$ to $$A.$$
5. the number of surjective functions from $$A$$ to $$B.$$
6. the number of surjective functions from $$B$$ to $$A.$$

Example 2

Let $$A = \left\{ {1,2,3} \right\}$$ and $$B = \left\{ {a,b,c,d,e} \right\}.$$
1. What is the total number of functions from $$A$$ to $$B?$$
2. How many injective functions are there from $$A$$ to $$B?$$
3. How many injective functions are there from $$A$$ to $$B$$ such that $$f\left( 1 \right) = a?$$
4. How many injective functions are there from $$A$$ to $$B$$ such that $$f\left( 1 \right) \ne a$$ and $$f\left( 2 \right) \ne b?$$

Example 3

Let $$A$$ and $$B$$ be sets of cardinality $$2$$ and $$3,$$ respectively. Which is greater – the number of functions from the power set of $$A$$ to set $$B$$ or the number of functions from set $$A$$ to the power set of $$B?$$

Example 4

Count the number of injective functions $$f:{\left\{ {0,1} \right\}^2} \to {\left\{ {0,1} \right\}^3}.$$

Example 5

Suppose $$\left| A \right| = 5$$ and $$\left| B \right| = 2.$$ Count the number of surjective functions from $$A$$ to $$B.$$

Example 6

Let $$\left| A \right| = 3$$ and $$\left| B \right| = 5.$$ How many functions are there from set $$A$$ to set $$B$$ that are neither injective nor surjective?

Example 1.

Let $$A = \left\{ {a,b,c,d} \right\}$$ and $$B = \left\{ {1,2,3,4,5} \right\}.$$ Determine:
1. the number of functions from $$A$$ to $$B.$$
2. the number of functions from $$B$$ to $$A.$$
3. the number of injective functions from $$A$$ to $$B.$$
4. the number of injective functions from $$B$$ to $$A.$$
5. the number of surjective functions from $$A$$ to $$B.$$
6. the number of surjective functions from $$B$$ to $$A.$$

Solution.

1. We see that $$\left| A \right| = 4$$ and $$\left| B \right| = 5.$$ The total number of functions $$f : A \to B$$ is given by ${\left| B \right|^{\left| A \right|}} = {5^4} = 625.$
2. The total number of functions $$f : B \to A$$ is ${\left| A \right|^{\left| B \right|}} = {4^5} = 1024.$
3. The number of injective functions from $$A$$ to $$B$$ is equal to ${\frac{{m!}}{{\left( {m – n} \right)!}} = \frac{{5!}}{{\left( {5 – 4} \right)!}} }={ 5! }={ 120.}$
4. There are no injections from $$B$$ to $$A$$ since $$\left| B \right| \gt \left| A \right|.$$
5. Similarly, there are no surjections from $$A$$ to $$B$$ because $$\left| A \right| \lt \left| B \right|.$$
6. The number of surjective functions $$f : B \to A$$ is given by the formula $$n!\,S\left( {m,n} \right).$$ Note that $$n$$ and $$m$$ are interchanged here because now the set $$B$$ is the domain and the set $$A$$ is the codomain. So, we have $n!\,S\left( {m,n} \right) = 4!\,S\left( {5,4} \right).$ The Stirling partition number $$S\left( {5,4} \right)$$ is equal to $$10.$$ Hence, the number of surjections from $$B$$ to $$A$$ is ${4!\,S\left( {5,4} \right) = 24 \cdot 10 }={ 240.}$

Example 2.

Let $$A = \left\{ {1,2,3} \right\}$$ and $$B = \left\{ {a,b,c,d,e} \right\}.$$
1. What is the total number of functions from $$A$$ to $$B?$$
2. How many injective functions are there from $$A$$ to $$B?$$
3. How many injective functions are there from $$A$$ to $$B$$ such that $$f\left( 1 \right) = a?$$
4. How many injective functions are there from $$A$$ to $$B$$ such that $$f\left( 1 \right) \ne a$$ and $$f\left( 2 \right) \ne b?$$

Solution.

1. The cardinalities of the sets are $$\left| A \right| = 3$$ and $$\left| B \right| = 5.$$ Then the total number of functions $$f : A \to B$$ is equal to ${\left| B \right|^{\left| A \right|}} = {5^3} = 125.$
2. The number of injective functions from $$A$$ to $$B$$ is equal to ${\frac{{m!}}{{\left( {m – n} \right)!}} = \frac{{5!}}{{\left( {5 – 3} \right)!}} }={ \frac{{5!}}{{2!}} }={ \frac{{120}}{2} }={ 60.}$
3. Since $$f\left( 1 \right) = a,$$ there are $$4$$ mapping options for the next element $$2:$$ $f\left( 2 \right) \in \left\{ {b,c,d,e} \right\}.$ Respectively, for the element $$3,$$ there are $$3$$ possibilities: ${f\left( 3 \right) }\in{ \left\{ {b,c,d,e} \right\}\backslash \left\{ {f\left( 2 \right)} \right\}.}$ Thus, there are $$4 \cdot 3 = 12$$ injective functions with the given restriction.
4. By condition,$$f\left( 1 \right) \ne a.$$ Then the first element $$1$$ of the domain $$A$$ can be mapped to set $$B$$ in $$4$$ ways: $f\left( 1 \right) \in \left\{ {b,c,d,e} \right\}.$ The next element $$2$$ cannot be mapped to the element $$b$$ and, therefore, has $$3$$ mapping options: ${f\left( 2 \right) }\in{ \left\{ {a,c,d,e} \right\}\backslash \left\{ {f\left( 1 \right)} \right\}.}$ There are no restrictions for the last element $$3$$. It can be mapped in $$3$$ ways: $f\left( 3 \right) \in B\backslash \left\{ {f\left( 1 \right),f\left( 2 \right)} \right\}.$ Hence, there are $$4 \cdot 3 \cdot 3 = 36$$ injective functions satisfying the given restrictions.

Example 3.

Let $$A$$ and $$B$$ be sets of cardinality $$2$$ and $$3,$$ respectively. Which is greater – the number of functions from the power set of $$A$$ to set $$B$$ or the number of functions from set $$A$$ to the power set of $$B?$$

Solution.

The power set of $$A,$$ denoted $$\mathcal{P}\left( A \right),$$ has $${2^{\left| A \right|}} = {2^2} = 4$$ subsets. The power set of $$B,$$ denoted $$\mathcal{P}\left( B \right),$$ has $${2^{\left| B \right|}} = {2^3} = 8$$ elements.

The number of functions from $$\mathcal{P}\left( A \right)$$ to $$B$$ is equal to

${{\left| B \right|^{\left| {\mathcal{P}\left( A \right)} \right|}} = {3^4} }={ 81.}$

Similarly, the number of functions from $$A$$ to $$\mathcal{P}\left( B \right)$$ is given by

${{\left| {P\left( B \right)} \right|^{\left| A \right|}} = {8^2} }={ 64.}$

Hence, the mapping $$f: \mathcal{P}\left( A \right) \to B$$ contains more functions than the mapping $$f: A \to \mathcal{P}\left( B \right).$$

Example 4.

Count the number of injective functions $$f:{\left\{ {0,1} \right\}^2} \to {\left\{ {0,1} \right\}^3}.$$

Solution.

The Cartesian square $${\left\{ {0,1} \right\}^2}$$ has $${\left| {\left\{ {0,1} \right\}} \right|^2} = {2^2} = 4$$ elements. Similarly, the $$3\text{rd}$$ Cartesian power $${\left\{ {0,1} \right\}^3}$$ has $${\left| {\left\{ {0,1} \right\}} \right|^3} = {2^3} = 8$$ elements.

The number of injective functions is given by

${\frac{{m!}}{{\left( {m – n} \right)!}} = \frac{{8!}}{{\left( {8 – 4} \right)!}} }={ \frac{{8!}}{{4!}} }={ 1680.}$

Example 5.

Suppose $$\left| A \right| = 5$$ and $$\left| B \right| = 2.$$ Count the number of surjective functions from $$A$$ to $$B.$$

Solution.

The total number of functions from $$A$$ to $$B$$ is

${\left| B \right|^{\left| A \right|}} = {2^5} = 32.$

To find the number of surjective functions, we determine the number of functions that are not surjective and subtract the ones from the total number.

A function is not surjective if not all elements of the codomain $$B$$ are used in the mapping $$A \to B.$$ Since the set $$B$$ has $$2$$ elements, a function is not surjective if all elements of $$A$$ are mapped to the $$1\text{st}$$ element of $$B$$ or mapped to the $$2\text{nd}$$ element of $$B.$$ Obviously, there are $$2$$ such functions. Therefore, the number of surjective functions from $$A$$ to $$B$$ is equal to $$32-2 = 30.$$

We obtain the same result by using the Stirling numbers. Given that $$S\left( {n,m} \right) = S\left( {5,2} \right) = 15,$$ we have

${m!\,S\left( {n,m} \right) = 2! \cdot 15 }={ 30.}$

Example 6.

Let $$\left| A \right| = 3$$ and $$\left| B \right| = 5.$$ How many functions are there from set $$A$$ to set $$B$$ that are neither injective nor surjective?

Solution.

First we find the total number of functions $$f : A \to B:$$

${\left| B \right|^{\left| A \right|}} = {5^3} = 125.$

Since $$\left| A \right| \lt \left| B \right|,$$ there are no surjective functions from $$A$$ to $$B.$$

Determine the number of injective functions:

${\frac{{m!}}{{\left( {m – n} \right)!}} = \frac{{5!}}{{\left( {5 – 3} \right)!}} }={ \frac{{5!}}{{2!}} }={ 60.}$

Hence the number of functions $$f : A \to B$$ that are neither injective nor surjective is $$125 – 60 = 65.$$