Calculus

Set Theory

Set Theory Logo

Counting Functions

Total Number of Functions

Suppose A and B are finite sets with cardinalities |A| = n and |B| = m. How many functions f : A → B are there?

Recall that a function f : A → B is a binary relation f ⊆ A × B satisfying the following properties:

Function as a binary relation between two sets.
Figure 1.

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

See solved problems on Page 2.

Page 1 Page 2