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 $m,n$ be positive integers. Let $X$ be a set with $m$ distinct elements and $Y$ with a set with $n$ distinct elements. How many distinct functions are there from $X$ to $Y$?

I was thinking the following:

If $n=m$, then there are $n!$ distinct functions. If $n>m$, then we have $nPm$ distinct functions ($P$ stands for permutation) and I am not sure about the case where $ n<m$. If $n<m$ the function $f$ should be a many-to-one function by the Pigeonhole principle, but I cannot enumerate the number of distinct functions for this case.

Any input, help and correction is much appreciated.

share|improve this question
    
You may find this relevant: en.wikipedia.org/wiki/Twelvefold_way –  Austin Mohr Oct 8 '12 at 18:14

4 Answers 4

up vote 4 down vote accepted

Hint: You answer seems to indicate that all functions are one-to-one. Note that this need not be the case.

share|improve this answer
    
Yes you are right on this, I take function as one-to-one to see if I can get any result, but it seems that the counting is more complicated than that. –  Daniel Oct 8 '12 at 17:52
3  
@jsk: Actually, it is much easier. For permutations (one-to-one functions) you remove an option at each stage. For arbitrary function, you do not remove options. You will have $n$ choices for $f ( \text{first element of }X)$, and then $n$ choices for $f ( \text{second element of }X)$, etc. –  Arthur Fischer Oct 8 '12 at 18:00
    
Is it $n \cdot m$ distinct functions? –  Daniel Oct 8 '12 at 18:14
    
Scratch my answer, that was totally wrong. –  Daniel Oct 8 '12 at 18:20
    
@jsk: yes, you were... a bit off. No worries, though, it's all a part of learning. –  Arthur Fischer Oct 8 '12 at 18:24

Hint 1: How many ways do you have to define $f(a)$ for $a\in X$ ?

Hint 2: two functions $f,g$ are different if there is $a\in X$ s.t the $f(a)\neq g(a)$

share|improve this answer

The answer is

$ n^m$.

Its the same as this question:

How many $m$-digit numbers can I form using the digits $1,2,\ldots,n$ and allowing repetition?

share|improve this answer
    
For every $x \in X$ I have $m$ elements from $Y$ to choose from and thus $n\cdot n \cdot n ... $ for $n^m$? –  Daniel Oct 8 '12 at 18:22
    
That's correct! A typo: $n$ elements from $Y$ to choose. –  P.. Oct 8 '12 at 18:37

It is worth noting that for two sets $X$ and $Y$ (not necessarily finite), the set of all functions $X \to Y$ is denoted by $Y^X$. One benefit of this notation is that, by generalising some of the arguments you've seen in the other answers, there is a nice expression for its cardinality, namely $$\left|Y^X\right| = |Y|^{|X|}.$$ In your situation $|X| = m$ and $|Y| = n$ so you get the result you've deduced above. What is really interesting is that the relationship between the cardinalities is true even for infinite sets (provided you use cardinal arithmetic).

share|improve this answer
    
Interesting! Thanks for the info! –  Daniel Oct 8 '12 at 22:27

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.