Show that there are less injective than surjective functions from A to B

Question

Title says it all. I need to show that there are less injective than surjective functions from A to B, A and B finite. Now, I know there are $\textrm{A}_{n}^{m}=\frac{n!}{(n-m)!}$ where |A|= m and |B|= n injective functions but I do not have any idea how to solve the problem.

Answer 1

Assuming that you are supposed to prove that there are fewer injective functions from $A$ to $B$ than there are surjective functions from $B$ to $A$...

Let $\mathcal I$ be the set of injections $A\to B$ and let $\mathcal S$ be the set of surjections $B\to A$. Then you can give an injection $\phi:\mathcal I\to \mathcal S$ as follows. Arrange the elements of $B$ in a circle. Given an injection $f:A\to B$, divide the circle of elements of $B$ into $|A|$ arcs, where the clockwise-most element of each arc is in the image of $f$. Then $\phi(f):B\to A$ is the map which sends each element of $b$ to the $a\in A$ for which $f(a)$ is the clockwise endpoint of the arc containing $b$.

To see that $\phi$ is injective, note that $f$ can be recovered from $g=\phi(f)$ as follows: for any $a\in A$, $g^{-1}(\{a \})$ will be a contiguous arc whose clockwise-most element is $f(a)$.