2
$\begingroup$

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

  • 2
    Funny remark for someone named « André... »2012-07-26

2 Answers 2

10

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

  • 1
    I see my mistake. I was just counting the possible mappings, and not the functions themselves.2012-07-26
2

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.