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

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

-

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.

-
Doh, the key insight was to count everything and subtract the non-surjections like in probability exercises (birthday paradox). Can't believe I didn't think of that. +1 and accept. Thanks for your help! –  Legendre Oct 19 '12 at 5:08
@Legendre: You’re welcome! –  Brian M. Scott Oct 19 '12 at 5:09

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\}$.

-
Very clean and elegant! –  Asaf Karagila Oct 18 '12 at 15:36
Very clean indeed. Thanks for your help. –  Legendre Oct 19 '12 at 6:00

Using PIE one can find a more generalized form of the number of surjections. The number of surjections of a set containing $m$ elements onto a set containing $n$ elements ($m>n$) is

$$\sum\limits_{i=0}^{n}(-1)^{i}\dbinom{n}{i}(n-i)^{m}$$

In the given question $n=3$ and $m=n$.

-
This in my language (Portuguese) is "combinção completa" and is equivalent to solve $$x + y + z = n$$ where $x,y,z$ are integer $\ge 0$ with $x,y,z \ge 1$ (to be surjectve) because you can represents the solutions by a scheme of balls and traces. Thus, doing $x=1 +a, y=1+b$ and $z = 1+c$, we have $a+b+c =n+3$. Therefore, the solution is $CR^{n+3}_{3}= \binom{(n+3)+(3)-1}{n+3}= \binom{n+5}{n+3}$. ($CR^{n+3}_{3}$ is notation in my book in Portuguese.)