how many distinct function are there from set A to B to C

Question

How many functions can be defined as A->B->C? I understand that there are |B|^|A| functions defined as A->B, and |C|^|B| functions defined as B->C, but for A->B->C, will there be |B|^|A| * |C|^|B| or (|C|^|B|)^(|B|^|A|) functions? Thank you!

Answer 1

Keeping in mind that the only thing that distinguishes one function as being "different" from another function is just how inputs get mapped to outputs. The "path" that an input travels along to get to its output does not matter in the slightest.

As such for $A=\{a_1,a_2\}, B=\{b_1,b_2\}, C=\{c_1\}$ there is only one function $\begin{cases} a_1\mapsto c_1\\ a_2\mapsto c_1\end{cases}$ despite there being many different "paths" that could arrive at this outcome.

The four functions $\begin{cases}a_1\mapsto b_1\mapsto c_1\\ a_2\mapsto b_1\mapsto c_1\end{cases},\begin{cases}a_1\mapsto b_1\mapsto c_1\\ a_2\mapsto b_2\mapsto c_1\end{cases},\begin{cases}a_1\mapsto b_2\mapsto c_1\\ a_2\mapsto b_1\mapsto c_1\end{cases},\begin{cases}a_1\mapsto b_2\mapsto c_1\\ a_2\mapsto b_2\mapsto c_1\end{cases}$ are all technically the same function in the end.

We are limited in the number of possible elements in the codomain being mapped to by the sizes of $|B|$ and $|A|$. There cannot be more elements in the image than either of $|B|$ or $|A|$ since $|Dom(f)|\geq |Rng(f)|$

Approaching via cases:

Suppose there are exactly $k$ elements in the image. Each of these elements has a set of elements as a preimage in $A$.

• Find the number of unordered partitions of $A$ into exactly $k$ non-empty sets. This can be done in $\left\{\begin{smallmatrix}|A|\\k\end{smallmatrix}\right\}$ ways where $\left\{\begin{smallmatrix}n\\r\end{smallmatrix}\right\}$ is the stirling number of the second kind.

• Pick which $k$ elements of $C$ are used in the range. This can be done in $\binom{|C|}{k}$ number of ways.

• match each part in the partition to an element of the image via a permutation. This can be done in $k!$ number of ways.

Applying multiplication principle, there are exactly $\left\{\begin{smallmatrix}|A|\\k\end{smallmatrix}\right\}\binom{|C|}{k}k!$ functions from $A$ to $C$ with $k$ elements in the image.

Ranging over all possible values of $k$ and remembering that $k$ cannot exceed $|B|$ we have for a final total:

$$\sum\limits_{k=1}^{|B|}\left\{\begin{smallmatrix}|A|\\k\end{smallmatrix}\right\}\binom{|C|}{k}k!$$

(note: we could rewrite the top limit on the summation as $\min\{|A|,|B|,|C|\}$ but this is unnecessary because any $k$ which exceeds $|A|$ or $|C|$ will cause the term to be zero anyways in the calculation of the stirling number or the binomial coefficient)