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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

What is the number of surjective (onto) functions from the set [3] to the set [3].

share|cite|improve this question

marked as duplicate by Gerry Myerson, Sasha, Paul, Micah, Hagen von Eitzen Feb 9 '13 at 7:59

This question was marked as an exact duplicate of an existing question.

We first count the complement. There are $2^5$ functions that "miss" $1$, also $2^5$ that miss $2$, and $2^5$ that miss $3$. Add. We get $3\cdot 2^5$.

But we have double-counted the functions that miss both $1$ and $2$, also the functions that miss $2$ and $3$, also the functions that miss $3$ and $1$. There is $1$ (or if you prefer, $1^5$) of each kind, so we subtract $3\cdot 1^5$.

Thus the total number of onto functions is $3^5-3\cdot 2^5+3\cdot 1^5$.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.