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.

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|improve this question
1  
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

1 Answer 1

up vote 4 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|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
1  
@JustinD. The answer is correct now. –  Rustyn Sep 21 '13 at 22:49

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.