Intereting Posts

For what integers $n$ does $\phi(2n) = \phi(n)$?
When do we use entailment vs implication?
Why study Galois Representations?
The axiom of choice in terms of cardinality of sets
Integral that arises from the derivation of Kummer's Fourier expansion of $\ln{\Gamma(x)}$
How many isomorphisms are there from $\Bbb Z_{12}$ to $\Bbb Z_{4} \oplus \Bbb Z_{3}$?
Cardinality of subtraction of sets
$A^2X = X$ show that $AX = X$, if $A_{ij} > 0$ and $x_{i} > 0$
Why is $e$ close to $H_8$, closer to $H_8\left(1+\frac{1}{80^2}\right)$ and even closer to $\gamma+log\left(\frac{17}{2}\right) +\frac{1}{10^3}$?
Volume of n-dimensional convex hull
Is it possible to solve this equation analytically?
Is There Something Called a Weighted Median?
Proving that $(\forall\epsilon>0)(\exists n,k\in\mathbb{N})(|\frac{n}{k}-\pi|<\frac{\epsilon}{k})$
Difficulty in proving this inequality
Looking for an intuitive explanation why the row rank is equal to the column rank for a matrix

I’ve gotten stuck at the following exercise;

There are

mfunctions 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 ofT(n)of

functions from ann-element set to {1, 2, …,m}. Solve the recurrence.

I’m not sure how to begin solving it?

- Finding a generating function of a series
- Prove that if $A\triangle B = C\triangle B$, then $A = C$
- prove that one of the digits $1,2,\dots,9$ occurs infinitely often in the decimal expansion of $\pi$
- Prove that $h< \frac{(k+l)^{k+l}}{(k^{k}l^{l})}$.
- What is the combinatorial proof for the formula of S(n,k) - Stirling numbers of the second kind?
- Monty Hall Problem with Five Doors

- If $a, b, q, r \in \mathbb{Z}$ such that $a = bq + r$. Prove $\gcd(a,b) = \gcd(b, r).$
- What is $f(f^{-1}(A))$?
- Mathematical Induction for Recurrence Relation
- Stirling numbers of the second kind on Multiset
- How do you derive the continuous analog of the discrete sequence $1, 2, 2, 3, 3, 3, 4, 4, 4, 4, …$?
- Base Cases in proving Zeckendorf's Theorem by Strong Induction
- Are these two predicate statements equivalent or not?
- How to Determine if a Function is One-to-One
- Proving a real valued function is periodic, and sketching it using obtained information
- how to see the logarithm as the inverse function of the exponential?

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.

- The Dihedral Angles of a Tetrahedron in terms of its edge lengths
- Distance is (uniformly) continuous
- If $G/Z(G)$ is cyclic, then $G$ is abelian
- Symmetries of a Pentagon.
- Let $(a_n)$ be a convergent sequence of positive real numbers. Why is the limit nonnegative?
- A perfect set results by removing the intervals in such a way as to create no isolated points.
- Bivariate polynomials over finite fields
- Minimum and Maximum eigenvalue inequality from a positive definite matrix.
- Laplace Operator in $3D$
- Proof of Hasse-Minkowski over Number Field
- Prove $E((X+Y)^p)\leq 2^p (E(X^p)+E(Y^p))$ for nonnegative random variables $X,Y$ and $p\ge0$
- Smallest positive element of $ \{ax + by: x,y \in \mathbb{Z}\}$ is $\gcd(a,b)$
- How many numbers of 6 digits, that can be formed with digits 2,3,9. And also divided by 3?
- $H$ is a maximal normal subgroup of $G$ if and only if $G/H$ is simple.
- Lattice paths and Catalan Numbers