Question

b) Read Section 2.3.6 (on page 161) of the 8'th edition of Rosen's book on partial functions. Let A and B be finite sets, with |A| = m and |B| = n. Calculate the number of partial functions f: A -> B.

Answer 1

A partial function f rom $A$ to $B$ is a map from $X \subset A$ to $B$ . If $X$ has $k$ elements such that $0 \leq k \leq n$ . So there are $n^k$ of such map.

In addition, there will be $\begin{pmatrix} m\\ k \end{pmatrix}$ subsets of $A$. So, the number of partial functions will be;

$\sum_{k=0}^m\begin{pmatrix} m\\ k \end{pmatrix}n^k=(1+n)^m$