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.

Let $X$ be a set with $N$ elements, and $Y$ a set with $M$ elements. What is the count of possible functions from $X$ to $Y$?

If answer is $M^N$, then why can't it be $N \times M$? That is, why not count for each $x \in X$, the possible mappings from $x$ to each $y\in Y$?

share|improve this question
    
That's exactly what you do. For each $x \in X$, there are $M$ possibilities for $f(x)$. So you make $N$ choices, each of which is a choice from one of $M$ possibilities... –  Qiaochu Yuan Jul 26 '12 at 19:45
1  
So, for each $x$ in $X$, you have $M$ possibilities. And you have to choose, from among $M$ possibilities, $N$ times. That means that you are choosing $M$, and you are doing so $N$ times. That's $M^N$, not $MN$. (If you have three choices, and you need to make the three choices four times, you have $81$ ways of doing it, not $12$). –  Arturo Magidin Jul 26 '12 at 19:45
1  
Let $Y=\{a,b,c,\dots,z\}$, and let $X=\{1,2,3,4,5\}$. There are just as many functions from $X$ to $Y$ as there are $5$-letter "words" over our alphabet. –  André Nicolas Jul 26 '12 at 21:03
1  
Funny remark for someone named « André... » –  PseudoNeo Jul 26 '12 at 22:18

2 Answers 2

up vote 7 down vote accepted

Say you need to determine what you will drink with your meals at home tomorrow. There are two meals, breakfast and dinner. And you have three options of drink for each meal: milk, water, and beer.

Now, this is the same as having a function

$f\colon\{$ breakfast, dinner$\}\to\{$ milk, water, beer$\}$.

How many different combinations of drinks can you have? It's more than $2\times 3=6$ combinations; it's $3^2=9$ combinations:

  1. Milk at both breakfast and dinner;
  2. Milk at breakfast, water at dinner;
  3. Milk at breakfast, beer at dinner;
  4. Water at breakfast, milk at dinner;
  5. Water at both breakfast and dinner;
  6. Water at breakfast, beer at dinner;
  7. Beer at breakfast, milk at dinner;
  8. Beer at breakfast, water at dinner;
  9. Beer at both breakfast and dinner.

As you see: three choices for what to do for breakfast, and three choices for what to do at dinner, for a total of $3\times 3 = 3^2$ possible outcomes.

If you had to plan for $N$ different meals, and you had $M$ choices for each meal? $M$ possible choices for the first, $M$ possible choices for the second, and so on. In the end, do you have $N\times M$, or do you have $M^N$?

share|improve this answer
    
I see my mistake. I was just counting the possible mappings, and not the functions themselves. –  Not a NaN notha Jul 26 '12 at 22:17

Enumerate the elements of $X$, $\{x_1, x_2, \cdots , x_n\}$. For $f(x_1)$ you have a choice of $M$ elements. The same applies to $f(x_2)$. Continue in this fashion $M$ times. As a result you have $M^N$ elements.

share|improve this answer

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.