Calculus

Set Theory

Set Theory Logo

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.\)
Function as a binary relation between two sets.
Figure 2.

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.\)

Counting surjective functions
Figure 2.

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.\)