# Calculating number of possible functions

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.

-

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

-

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.

-
About the example you gave to brush up my mind, if A has 1 element then I can make only one function independent of the number of elements of B. For A having 2 elements I can make 2 functions. Am I right? –  Fahad Uddin Sep 11 '11 at 7:15
I'm afraid not. Here is one function from $A=\{x\}$ to $B=\{z_1,\ldots,z_n\}$: $$f_1:A\to B\text{ defined by }f(x)=z_1$$ Here is a different function from $A$ to $B$: $$f_2:A\to B\text{ defined by }f(x)=z_2$$ Do you see how many functions there are from $A=\{x\}$ to $B=\{z_1,\ldots,z_n\}$? –  Zev Chonoles Sep 11 '11 at 7:18
[I accidentally upvoted the first comment instead of the second. Unfortunately, the software does not allow me to roll this back.] –  Rasmus Sep 11 '11 at 7:21
But these are the two relations that you made, if both of them are present in a single function then a single input x will give rise to two outputs i.e z1 and z2 which is against the definition of a function. –  Fahad Uddin Sep 11 '11 at 7:24
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$. –  Zev Chonoles Sep 11 '11 at 7:26