# Why are there $n^m$ such functions?

A function from the set $A$ to the set $B$ is just a correspondance from each element of the set $A$ to an element of $B$.If $|A|=m$ and $|B|=n$,how many such functions exist?I saw that the solution is $n^m$..but why is it like that?

A set is a group of unique elements (in opposed to a multi-set).

A function $f : A \rightarrow B$ maps every element in the domain $A$ to a single element in the range $B$.

You have $m$ elements in the domain $A$ and $n$ elements in the range $B$.

Each element in the domain $A$ must be mapped to an element in the range $B$:

• The 1st element in the domain $A$ has $n$ mapping options in the range $B$
• The 2nd element in the domain $A$ has $n$ mapping options in the range $B$
• The 3rd element in the domain $A$ has $n$ mapping options in the range $B$
• ...
• The mth element in the domain $A$ has $n$ mapping options in the range $B$

So the total number of different mappings (i.e., functions) from $A$ to $B$ is: $$n \times n \times n \times \dots \times n = n^m$$

• I understand!!!Thank you!!! – evinda Apr 24 '14 at 19:23
• @evinda: You're welcome :) – barak manos Apr 24 '14 at 19:32

There are $n$ ways to map a single element from $A$ into $B$. The number of ways to map two elements from $A$ into $B$ is $n\times n$. To see this, consider $A=\{1,2\}$ and $B=\{1,2\}$ then you can do:

$1\mapsto 1, 2\mapsto 1$

$1\mapsto 1, 2\mapsto 2$

$1\mapsto 2, 2\mapsto 1$

$1\mapsto 2, 2\mapsto 2$

Now generalise this to $m$ elements from $A$ to $B$: it is $n\times n\times\dots\times n=n^m$.

• I understand!!!Thanks!!! – evinda Apr 24 '14 at 19:23