Counting Functions

Solved Problems

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

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.

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

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

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

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

Solution.

The total number of functions from \(A\) to \(B\) is

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

Solution.

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

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

Determine the number of injective functions:

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