2
$\begingroup$

Let $A = \{1, 2, 3, 4\}$ and $B = \{a, b, c\}$

How many surjective functions are there from $A \to B$?

My first thought is 3*3*2*1, but I've already written 19 out by hand.

$\endgroup$
  • $\begingroup$ See here for a neat general discussion. $\endgroup$ – Shailesh Sep 21 '15 at 3:06
7
$\begingroup$

We will use Inclusion/Exclusion.

There are $3^4$ functions from $A$ to $B$. From $3^4$ we must subtract the number of functions that are not surjective.

There are $2^4$ functions from $A$ to $\{a,b\}$, also $2^4$ from $A$ to $\{b,c\}$, also $2^4$ to $\{a,c\}$.

So are there $3\cdot 2^4$ non-surjective functions? No, because $2^4+2^4+2^4$ double-counts the $3$ constant functions. So the number of non-surjective functions is $3\cdot 2^4-3$.

Remark: The idea generalizes nicely. But with numbers as small as these, we can count in other ways.

Two of the numbers from $1$ to $4$ will be mapped to the same thing, and the others to different things. The two that are mapped to the same thing can be chosen in $\binom{4}{2}$ ways. What they are mapped to can be chosen in $3$ ways. And now there are $2$ ways to decide where the remaining two numbers go, for a total of $\binom{4}{2}\cdot 3\cdot 2$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

Consider the set $f^{-1}(a),f^{-1}(b),f^{-1}(c)$.Possible cardinalities of the sets should be say $2,1,1$ otherwise it fails to be surjective.

Let us assume first that $|f^{-1}(a)|=2$ then from the four choices we have $\{1,2,3,4\}$ we have $4C_2$ choices for $f^{-1}(a)$.

For $f^{-1}(b)$ we have $2$ choices and for $f^{-1}(c)$ only one .So we have $6\times 2\times 1$ choices .

repeating the arguements for $|f^{-1}(b)|=2$ and $|f^{-1}(c)|=2$ we have $12*3$ choices

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Your answer looks correct and is also the same as Andre's remark. $\endgroup$ – user21820 Sep 21 '15 at 3:35
  • $\begingroup$ Thank you for your comments @user21820 $\endgroup$ – Learnmore Sep 21 '15 at 5:14

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