Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer

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.

share|improve this answer
1  
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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