Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
For reference, this answer contains a general method for counting the number of surjective functions between two finite sets. – Ayman Hourieh Sep 21 '13 at 21:10
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. – JB King Sep 21 '13 at 23:24
up vote 6 down vote accepted

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

share|cite|improve this answer
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!$. – Justin D. Sep 21 '13 at 22:01
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.. – Rustyn Sep 21 '13 at 22:06
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$. – Justin D. Sep 21 '13 at 22:12
I'll think about it! – Justin D. Sep 21 '13 at 22:29
@JustinD. The answer is correct now. – Rustyn Sep 21 '13 at 22:49

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 ;)

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

protected by Zev Chonoles Mar 6 at 19:21

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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