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.

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.

share|improve this question
add comment

4 Answers

up vote 9 down vote accepted

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.

share|improve this answer
    
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
add comment

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

This in my language (Portuguese) is "combinção completa" and is equivalent to solve \begin{equation} x + y + z = n \end{equation} 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.)

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.