Counting the number of surjections.

How many functions from set $\{1,2,3,\ldots,n\}$ to $\{A,B,C\}$ are surjections? $n \geq 3$

Attempt

I was hoping to count the number of surjections by treating $A,B,C$ like bins, and counting the number of ways to fill them with $1,2,3,\ldots,n$ such that no bins are empty. This is equivalent to putting two "separator" bars in between the $n$ numbers or $n-1 \choose 2$.

However, I think I am missing a step here: prior to putting in the separator bars, I should permutate the $n$ elements. So, multiply by $n!$.

The order of elements in the same bins do not matter. So I should be divided by the number of permutations of the elements in each bins. This is where I am stuck.

Additional Info

I made the question up myself. Feel free to modify the question into a more solvable form if it is too difficult/complicated.

Solution 1:

You’ve actually made a pretty good start: your first idea doesn’t work, but it’s a reasonable one to try, and you’ve spotted the difficulty with it. What you want now is an inclusion-exclusion argument. There are $3^n$ functions altogether. $2^n$ of them are functions from $\{1,\dots,n\}$ to $\{A,B\}$, missing $C$ altogether, so we need to throw them out. There are also $2^n$ functions that miss $B$ and $2^n$ that miss $A$, so our improved approximation to the number of surjections is $3^n-3\cdot2^n$.

Unfortunately, we’ve now gone overboard. The function that sends every $k\in\{1,\dots,n\}$ to $A$, for instance, has been thrown out twice, once for not hitting $B$ and once for not hitting $C$. The same goes for the other two constant functions. We need to throw each of them back in once, so that on net we’ve thrown each of them out just once, not twice. The revised number of surjections is then

$$3^n-3\cdot2^n+3=3\left(3^{n-1}-2^n+1\right)\;.\tag{1}$$

A little thought should convince you that no further adjustments are required and that $(1)$ is therefore the desired number.

Solution 2:

Ignoring surjectivity, there are $3^n$ maps $\{1,2,\ldots,n\}\to \{A,B,C\}$. We should subtract the $2^n$ maps that ar actually just maps $\{1,2,\ldots,n\}\to \{A,B\}$, also the $2^n$ maps $\ldots\to \{A,C\}$ and the $2^n$ maps $\ldots\to \{B,C\}$. But now we have subtracted too much: The three constant maps $f(x)=A$, $f(x)=B$ and $f(x)=C$ where subtracted twice (e.g. $f(x)=A$ as a map $\to\{A,B\}$ and also as a map $\{A,C\}$). In summary there are therefore $$ 3^n-3\cdot 2^n+3$$ surjective maps $\{1,2,\ldots,n\}\to\{A,B,C\}$.