10
$\begingroup$

Am I on the right track? I am not sure about my reasoning...

Number of surjective functions from $A$ to $B$

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

We must count the surjective functions, meaning the functions for which for all $b \in B$, $\exists~a \in A$ such that $f(a) = b$, $f$ being one of those functions. In order for a function $f:A\rightarrow B$ to be a surjective function, all 3 elements of $B$ must be mapped.

We need to count how many ways we can map those 3 elements. We will subtract the number of functions from $A$ to $B$ which only maps 1 or 2 elements of $B$ to the number of functions from $A$ to $B$ (computed in 4.c : 81).

Only 1 element of $B$ is mapped

The first $a \in A$ has three choices of $b \in B$. The others will then only have one. Total functions from $A$ to $B$ mapping to only one element of $B$ : 3.

Exactly 2 elements of $B$ are mapped

Similarly, there are $2^4$ functions from $A$ to $B$ mapping to 2 or less $b \in B$. However, these functions include the ones that map to only 1 element of $B$. So there are $2^4-3 = 13$ functions respecting the property we are looking for.

In the end, there are $(3^4) - 13 - 3 = 65$ surjective functions from $A$ to $B$.

$\endgroup$
2
  • 1
    $\begingroup$ For reference, this answer contains a general method for counting the number of surjective functions between two finite sets. $\endgroup$ – Ayman Hourieh Sep 21 '13 at 21:10
  • $\begingroup$ The 2 elements ignores that there are 3 different ways you could choose 2 elements from B so in fact there are 39 such functions instead of 13, I believe. $\endgroup$ – JB King Sep 21 '13 at 23:24
16
$\begingroup$

$\left\lbrace{4\atop 3}\right\rbrace=6$ is the number of ways to partition $A$ into three nonempty unlabeled subsets. For each partition, there is an associated $3!$ number of surjections, (We associate each element of the partition with an element from $B$). Thus, the total number of surjections is $3! \times \left\lbrace{4\atop 3}\right\rbrace= 36.$

$\endgroup$
5
  • $\begingroup$ Why do you count the ways to map the other three elements? The way I see it is we place the first three elements with $3! {4 \choose 3}$. Then we add the fourth in the empty space. So I would not multiply by $3!$. $\endgroup$ – Justin D. Sep 21 '13 at 22:01
  • $\begingroup$ You can't "place" the first three with the $3! {4\choose 3}$-- I am confused by this... I do not understand what you mean.. $\endgroup$ – Rustyn Sep 21 '13 at 22:06
  • $\begingroup$ The way I see it (I know it's wrong) is that you start with your 3 elements and map them. You have 24 possibilities. Then you add the fourth element. It can be on a, b or c for each possibilities : $24 \cdot 3 = 72$. $\endgroup$ – Justin D. Sep 21 '13 at 22:12
  • $\begingroup$ I'll think about it! $\endgroup$ – Justin D. Sep 21 '13 at 22:29
  • 1
    $\begingroup$ @JustinD. The answer is correct now. $\endgroup$ – Rustyn Sep 21 '13 at 22:49
8
$\begingroup$

More generally, the number S(a,b) of surjective functions from a set A={1,...,a} into a set B={1,...,b} can be expressed as a sum :

$S(a,b) = \sum_{i=1}^b (-1)^{b-i} {b \choose i} i^a$

where ${b \choose i} = \frac{b!}{i! (b-i)!}$ is the number of different ways to choose i elements in a set of b elements.

To see this, first notice that $i^a$ counts the number of functions from a set of size $a$ into a set of size $i$. Therefore, our result should be close to $b^a$ (which is the last term in our sum). If we want to keep only surjective functions, we have to remove functions that only go into a subset of size $b-1$ in $B$. There are ${b \choose {b-1}}$ such subsets, and for each of them there are $(b-1)^a$ functions. If we just keep $b^a - {b \choose {b-1}} (b-1)^a$ as our result, there are some functions that we removed more than once, namely all functions that go into a subset of size $< b-1$. Therefore, we have to add them back, etc. This leads to the result claimed: $b^a - {b \choose {b-1}} (b-1)^a + {b \choose {b-2}} (b-2)^a - ...$

$\endgroup$
1
  • 1
    $\begingroup$ Here I just say that the above general formula for $S(a, b)$ is easily obtained by applying the inclusion–exclusion principle en.wikipedia.org/wiki/Inclusion–exclusion_principle to the subsets $A_i$ of $B^A$ consist of those maps don't have $i$ in their images. $\endgroup$ – Lao-tzu Jul 27 '19 at 9:11
2
$\begingroup$

This is an old question, but I recently came across the same problem and solved it in a different way which I find a bit easier to comprehend.

Say you have a $k$ letter alphabet, and want to find the number of possible words with $n_1$ repetitions of the first letter, $n_2$ of the second, etc. The equation for the number of possible words is, as demonstrated in this paper:

$$ P(n:n_1,n_2,...,n_k)=\frac{n!}{n_1!\times n_2! \times\cdots\times n_k!} $$

Now, think of the elements of $B$ as our alphabet of 3 letters, one of which is repeated in its mapping on to our 4 elements of $A$. Since the repeated letter could be any of $a$, $b$, or $c$, we take the $P(4:1,1,2)$ three times. Then the number of surjections is

$$ 3\times P(4:1,1,2)=36 $$

I came out with the same solution as the accepted answer, but I may still be erroneous somewhere in my reasoning. Please let me know if you see a mistake ;)

$\endgroup$
0
$\begingroup$

Let a(n,m) be the number of surjections of En = {1,2,...,n} to Em = {0,1,...,m}. Choose an element L of Em. This can be done in m ways. There are two possibilities. (1) L has 1 original in En (say K). The other (n - 1) elements of En are mapped onto the (m - 1) elements of Em (other than L). Number of ways mxa(n-1,m-1). (2) L has besides K other originals in En. The other (n-1) elements of En are in that case mapped onto the m elements of Em. Here is the number of ways mxa(n-1,m). Conclusion: we have a recurrence relation a(n,m) = m[a(n-1,m-1)+a(n-1,m)]. a(n,n) = n!, a(n,1) =1 for n>=1 and a(n,m)= 0 for m>n. One verifies that a(4,3)=36.

$\endgroup$
0

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