What is the formula to find the number of one-one functions from $A$ to $B$? Let $p$ be the number or elements in $A$.
Let $q$ be the number of elements in $B$.
If the number of functions from $A$ to $B$ is equal to $q^p$, then:


*

*What is the formula to find the number of one-one functions from $A$ to $B$?

*How about onto functions?

 A: *

*

Well, the only way for there to be any one to one functions $A\to B$ is for A to be smaller, ie: $p\leq q$.
In this case, choosing such a function is the same as choosing the $p$ elements of $B$ which are in the image of the map. Thus, the number of such maps is the number of ways to choose $p$ elements out of $q$ where order matters, since we care about the actual function not just it’s image. Thus there are
$\frac{q!}{(q-p)!}$ such maps.


*For onto maps $A\to B$, we now need $A$ to be at least as big as $B$, so $p\geq q$.

After similar counting, we can say that the number of such maps is equal to the number of ways of breaking a $p$ element set into $q$ nonempty subsets, corresponding to the fibers over the elements of $B$.
This is harder. These are called the Stirling numbers of the second kind, $s(p,q)$.
A: 1) Build a function and keep track of how many choices we have. Start with an element in $A$, you have $q$ choices for its image. Consider then a second element in $A$, to keep your function one-to-one you have only $q-1$ choices for its image. You will have then $q-2$ choices for an image of a third element of $A$ and so on... Up to $q-p+1=q-(p-1)$ choices for the $p$-th one. In conclusion you have $q(q-1)...(q-(p-2))(q-(p-1))=q!/(q-p)!$ possible injective functions. Of course this is possible only if $p\leq q$.
2) This is more complicated, but it has already been asked Calculating the total number of surjective functions.
A: If set A contains m elements and set B contains n elements, then the number of one-one functions from A to B is $^nC_m×m!$ as we consider the selection of m elements and these elements related to one-one to set A is m! so in total those two conditions will be multiplied to get the answer
