2
$\begingroup$

Here is a question,

If A has m elements and B has n elements, how many functions are there from A to B?

What I came came up first was m into n functions. After revising the question, I came up with the answer n. Can someone please help me out with it? Thanks.

2 Answers 2

2

There are $n^m$ functions from $A$ to $B$.

In regard to your comment in Zev Chonoles response : suppose $A$ has a single element $a$ and $B$ has two element $i$ and $j$. There are two functions from $A$ to $B$. They are

$f_1(a) = i$

and

$f_2(a) = j$

Now for the more general statement (where $m$ and $n$ are finite). There are $m$ elements of $A$. To each element of $A$, you must assign an element of $B$. For any element of $A$, you have $n$ choices of things in $B$ to which to map that element. There are $m$ element in $A$ for which you must assign something in $B$. By some fundamental counting principle, there are $n^m$ number of possibilities.

In the spirit of the finite case, the set of all functions from $A$ to $B$ is called $B^A$.

3

Hint: A function $f:A\to B$ is defined by choosing, for each element $x\in A$, an element $f(x)\in B$ for $x$ to go to. There are $n$ elements of $B$ to choose from, for each element of $A$. There are $n$ elements of $A$. The choices are independent (where you choose to send $x\in A$ has no bearing on where you can choose to send a different $y\in A$).

Consider the fact that if you have two choices to make, and choice 1 has $d_1$ options and choice 2 has $d_2$ options, if the choices can be made independently then you have $d_1\times d_2$ options overall.


It may help to work out some simple cases first. Suppose $A$ has just 1 element. How many functions $f:A\to B$ are there, if $B$ has $n$ elements?

$A=\{x\}\qquad\longrightarrow\qquad B=\left\{\matrix{z_1\\ z_2\\ \vdots\\ z_n}\right\}$

What about if $A$ has two elements, say $A=\{x,y\}$? Then a function $f:A\to B$ is uniquely determined by choosing $f(x)\in B$ and $f(y)\in B$, and the choices are independent.

  • 1
    I specified two different functions. Do you agree that the function $f:\mathbb{R}\to\mathbb{R}$ that takes a real number $x$ and outputs $f(x)=x^2$ is a different function from $g:\mathbb{R}\to\mathbb{R}$ that takes $x$ and outputs $g(x)=x+1$? Likewise, I first defined one function $f_1:A\to B$, then a **different** function $f_2:A\to B$. There is no conflict on where to send $x$.2011-09-11