0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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$$

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

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$.

$\endgroup$
  • $\begingroup$ I understand!!!Thanks!!! $\endgroup$ – evinda Apr 24 '14 at 19:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.