Can anyone explain or/and provide a proof of the following statement?

Question

Can anyone explain or/and provide a proof of the following statement?

I am reading a book on Combinatorics. In the book the author provides the following statement along with an explanation:

The cardinality of the set of all the functions from an n-set to an m-set is $m^n$.

The explanation given is:

Let $D = \{1, 2 .... , n\}$ be the n-set and let $R = \{r_1, r_2, ....., r_m\}$. Given any function $f$ from $D$ to $R$, we write down the sequence $(f(1), f(2), ... , f(n))$ of length $n$ with entries from $R$.

I am not able understand the explanation so I am looking for a more elaborate or a more visual proof/explanation of the statement.

Answer 1

A function from a set $A$ to a set $B$ assigns to every element in $A$ precisely one element in $B$. If $A=\{a_1,\ldots,a_n\}$ and $B=\{b_1,\ldots,b_m\}$, this means that for every $a_i$ we can choose one of the $b_1,\ldots, b_m$ as its image.

Lets give an easy example. Suppose you have bought two plain white t-shirts $t_1$ and $t_2$ from the store, and you have bought three different colours of paint; blue, yellow and red. Then the a function from $T=\{t_1,t_2\}$ to $C=\{$blue, red, yellow$\}$ is a choice of a color for each shirt. For the first shirt $t_1$ there are $3$ different choices. For the second shirt $t_2$ there are again $3$ choices. These choices are mutually independent so we get $3\times 3=3^2$ choices of functions.

We can generalise this to $n$ t-shirts $t_1,\ldots, t_n$ and $m$ colours $c_1,\ldots, c_m$. For the first shirt we can choose between all the $m$ colours, for the second shirt we can again choose between all these colours, and so we end up with $m\times m\times \ldots \times m$ different combinations, which is precisely $m^n$.

Answer 2

It may help to consider some small examples. For example, $m=2, n=3$: let $A=\{a,b,c\}$ and $B=\{x,y\}$. Here are all the maps $A\to B$ (all $2^3=8$ of them):

$$\begin{pmatrix}a&b&c\\x&x&x\end{pmatrix}$$ $$\begin{pmatrix}a&b&c\\x&x&y\end{pmatrix}$$ $$\begin{pmatrix}a&b&c\\x&y&x\end{pmatrix}$$ $$\begin{pmatrix}a&b&c\\x&y&y\end{pmatrix}$$ $$\begin{pmatrix}a&b&c\\y&x&x\end{pmatrix}$$ $$\begin{pmatrix}a&b&c\\y&x&y\end{pmatrix}$$ $$\begin{pmatrix}a&b&c\\y&y&x\end{pmatrix}$$ $$\begin{pmatrix}a&b&c\\y&y&y\end{pmatrix}$$

To generalise: for the first element in $A$ you have $m$ choices (in this case, you could've chosen $a\mapsto x$ or $a\mapsto y$). For each of those choices, you have $m$ choices to map the second element of $A$. This gives you $m^2$ different maps of the first two elements. For each of those, you have $m$ ways to map the third element - in total $m^3$ maps for the first three elements. And so on - eventually you conclude that the number of maps of all $n$ elements of $A$ is $m^n$.

Answer 3

Every such sequence $(f(1),...,f(n))$ determines a function $f: D \to R,$ and all such functions can be obtained in this way. For each value of $f$, or in other words, for each sequence element, there are $m$ choices. Since we need to define $f$ on $n$ elements, there are in total $m \times m \times ... \times m = m^n$ possible functions $f$.

Another way to phrase it: to define $f$ is the same as to specify its values on $D,$ and there are $m^n$ distinct ways to do this.

Answer 4

Let $D = \{1, 2 .... , n\}$ be the n-set and let $R = \{r_1, r_2, ....., r_m\}$, and let $f: D \to R$ be a function from $D$ to $R$. The first element $1$ can be sent by $f$ in any element of $R$, meaning that you have $m$ possible images (for $1$). For $2$ the same concept applies, and so for every possible image of $1$, there are $m$ choices for the image of $2$, and in total $m\times m$ possible combinations for both the images of $1$ and $2$. You can now prove the statement by induction.