# The count of functions from $X$ to $Y$?

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

-
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
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
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
Funny remark for someone named « André... » –  PseudoNeo Jul 26 '12 at 22:18

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

-
I see my mistake. I was just counting the possible mappings, and not the functions themselves. –  T. Webster 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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 1, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.74356609582901, "perplexity": 256.5542109664183}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.3, "absolute_threshold": 10, "end_threshold": 5, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-22/segments/1432207924991.22/warc/CC-MAIN-20150521113204-00033-ip-10-180-206-219.ec2.internal.warc.gz"}