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?

The 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 \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!$$