3
$\begingroup$

"Find the number of surjective functions $f: A->B$, where$ A = \{1,2,3,4,5,6\}, B = \{1,2,3,4\}$ and where $f(1) > f(2) > f(3)$."

I know how to find # of surj. functions from $ A->B $ (in this case $4^6 $minus all maps to subsets of B). But I don't know how to implement this condition$ f(1) > f(2) > f(3)$.

I think it is important to calculate maps of $\{1, 2, 3\}$, I have found 4 ways how to do the mapping, simply by writing all the possible ways (I think it is 4 choose 3 since there is only one way how to order). Then I need to assign some $(>=1)$ elements from $\{4, 5, 6\}$ to the remaining element of $B$ (for the function to be surjective) and keep in mind that $\{4, 5, 6\}$ can also be assigned to other els of$ B$.

Can you please give me an advice how to do it? Thank you

1 Answers 1

3

You're on the right track. Now just observe that the number of ways to map $4$, $5$ and $6$ such that the missing element is covered is the total number of ways to map them minus the number of ways to map them to one fewer element.

  • 1
    I see! It is 4 * (4^3 - 3^3). 4^3 is number of ways how to map remaining els MINUS the ways how to map remaining elements without mapping to the one element of B.2012-10-26