Take the 2-minute tour ×

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

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

Your Answer


