Number of functions from n-element set to {1, 2, …, m}

I’ve gotten stuck at the following exercise;

There are m functions from a one-element set to the set {1, 2, …, m}.
How many functions are there from a two-element set to {1, 2, …, m}?
From a three-element set? Give a recurrence for the number of T(n) of
functions from an n-element set to {1, 2, …, m}. Solve the recurrence.

I’m not sure how to begin solving it?

Solutions Collecting From Web of "Number of functions from n-element set to {1, 2, …, m}"

First you should try to look at the case of functions $\{1,2\}\to \{1,..,m\}$. Note that there are no restrictions one where you can map the two points in your domain. So there are $m$ options to mapping $1$ and $m$ options for mapping $2$. So together there are $m\cdot m$ options.

If you get that, then try doing that for 3 points, And then see if you can generalise it for $n$ points. And if not i have written an explanation in the following:

Let’s look at the function $$f:\{1,…,n\}\to \{1,…,m\}$$Take $1\le i\le n$. there are $m$ elements in $\{1,…,m\}$ so there are $m$ options for mapping $i$ to. i.e $m$ options to define $f(i)$. Thee are $n$ elements in the domain, so there are $m^n$ options to define $f$. i.e there are $m^n$ many such functions.


Edite: I think that a more intuitive way to think about this problem is by looking at these functions as $n$-tuples or “vetoers” . Indeed a function $f:\{1,…,n\}\to \{1,…,m\}$ can be viewed as the ordered $n$-tuple $$(f(1),f(2),..,f(n))$$

From $\{1,…,m\}^n$. (by $A^n$ we mean $A\times …\times A$ when the product is taken $n$ many times)

The important part here is that you can chose the value of any element in the domain to be any element in the range under the function operation. That is since we do not require the function to be subjective or injective. (in thous cases we will need to take a more delicate approach) Thus in any $n$-tuple from $\{1,…,m\}^n$ will represent a function! So we have a bijective relation between our functions and elements of $\{1,…,m\}^n$, and so the problem is translated to **How many $n$-tupls are there in $\{1,…,m\}^n$ ** Or more accurately what is the size of $\{1,…,m\}^n$? And that should be easier i believe.

sha has ably explained how to find an explicit formula for the number of functions from a set with $n$ elements to a set with $m$ elements. I will address the recurrence relation.

Without loss of generality, we will take the $n$ element set to be the set $[n] = \{1, 2, 3, \ldots, n\}$.

The number of functions from $f: \{1\} \to [m]$ is $m$ because there are $m$ possible choices for $f(1)$. Hence, $T(1) = m$.

The number of functions from $f: \{1, 2\} \to [m]$ is $m^2$ since for each of the $m$ ways $f(1)$ can be assigned, there are $m$ ways to assign $f(2)$, yielding $m \cdot m = m^2$ possible functions. Hence, $T(2) = m^2$.

Let $n \geq 2$. Suppose that the number of functions $f: [n – 1] \to [m]$ is $T(n – 1)$. Then the number of functions $f: [n] \to [m]$ is $mT(n – 1)$ since for each of the $T(n – 1)$ ways of assigning the values of $f(1), f(2), \ldots, f(n – 1)$, we can assign $f(n)$ in $m$ ways.

Therefore, we have the recurrence relation
\begin{align*}
T(1) & = m\\
T(n) & = mT(n – 1), n \geq 2
\end{align*}
Evaluating the recurrence for the first few values of $n$ yields
\begin{align*}
T(1) & = m\\
T(2) & = mT(1) = m \cdot m = m^2\\
T(3) & = mT(2) = m \cdot m^2 = m^3
\end{align*}
which suggests that the explicit formula for $T(n) = m^n$, which can be proved by induction.