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 $[n]$ be the set of integers $\{1, 2, \ldots, n\}$. I want to find the number of onto functions from $[m]$ to $[3]$. The answer I found was $3!\cdot (3)^{m-3}$

My reasoning is:

We have a $2$-step independent process:

Step 1: create a bijective mapping from the first three elements of $[m]$ to the elements of $[3]$. This can happen in $3!$ ways.

Step 2: The remaining $m-3$ elements each have $3$ possible mappings to a $n \in [n]$ and each choice is independent. So we have: $3^{m-3}$ possible mappings.

By the product rule we have: $3!\cdot 3^{m-3}$

  1. Is my answer correct?
  2. Is my reasoning correct?

EDIT I see that the above is undercounting, how about this way of thinking. I will start by showing my interpretation and then deriving the steps and counting:

So, I have $m$ positions, and each position must have a number $1, 2, or 3$. This is subject to the constraint where $1, 2, and 3$ must occur at least once (onto).

Step 1: Out of the $m$ positions I need to place $1, 2, or 3$, where order matters. This is P$(m, 3) = \dfrac{m!}{(m-3)!}$.

Step 2: The remaining $m-3$ positions each have $3$ possible ways of occurring. So we have $3^{(m-3)}$ ways of this occurring.

Now, we will multiply: $\dfrac{m!}{(m-3)!}\cdot 3^{m-3}$

Finally, we must divide by $2!$ since we created an ordering here and would be then counting each step more than once.

Final Answer: $\dfrac{\dfrac{m!}{(m-3)!}\cdot 3^{m-3}}{2!}$

  1. Is this correct?
share|improve this question
1  
Why are you assuming that the mapping sends $1,2$, and $3$ to distinct elements of $[3]$? If $n\ge 5$, it might send all three of them to the same element of $[3]$. –  Brian M. Scott Jan 23 '13 at 1:42
    
The answer you typed at the top is different from the answer that you typed at the bottom. –  Calvin Lin Jan 23 '13 at 1:49
    
Yes, I see now that I am undercounting. –  CodeKingPlusPlus Jan 23 '13 at 1:53
    
It is not easy to see how to use the idea to get a correct count. –  André Nicolas Jan 23 '13 at 2:05
    
@AndréNicolas, is my edit correct now? –  CodeKingPlusPlus Jan 23 '13 at 2:53
add comment

1 Answer 1

  1. Your answer is incorrect. As $m$ tends to infinity, almost every function should be onto, so your answer should be asymptotically close to $3^m$.

  2. Your reasoning is incorrect. Think about approaching this problem using the Principle of Inclusion and Exclusion.

share|improve this answer
add comment

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.