Calculus

Set Theory

Set Theory Logo

Counting Functions

Solved Problems

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. There are no injections from \(B\) to \(A\) since \(\left| B \right| \gt \left| A \right|.\)
  4. Similarly, there are no surjections from \(A\) to \(B\) because \(\left| A \right| \lt \left| B \right|.\)
  5. 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\}.\]
    If \(f\left( 1 \right) = b,\) then \(f\left( 2 \right)\) has \(4\) mapping options:
    \[f\left( 2 \right) \in \left\{ {a,c,d,e} \right\}.\]
    If \(f\left( 1 \right) \in \left\{ {c,d,e} \right\},\) then \(f\left( 2 \right)\) 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\). In all cases 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 \(\left(4 + 3 \cdot 3\right) \cdot 3 = 12+27 = 39\) 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.\)

Page 1 Page 2