Number of One-to-One Functions I have a homework question I have been struggling with  which is: 
How many one-to-one functions are there from the set $A$ into the $B$ if $|A|=n$
and $|B| = k$?
I can't seem to think of the way to attack this problem help will be appreciated :)
Thanks 
 A: If $n>k$ then obviously there are none.
Suppose that $n\le k$, then we can ask ourselves how many functions are there which are one-to-one.
Well, how does a one-to-one function looks like? Its range is a set of exactly $n$ distinct elements from $B$, and every possible permutation of $A$ will give us a different function with the same range.
The number of $n$ elements sets from $k$ is ${k\choose n}=\frac{k!}{n!(k-n)!}$, and there are $n!$ possible permutations for $A$. 
Therefore we have ${k \choose n}\cdot n! = \frac{k!}{(k-n)!}$ many one-to-one functions from $A$ into $B$. Of course, if you did not mean functions, and just meant "sets of $n$ distinct elements" the answer is ${k\choose n}=\frac{k!}{n!(k-n)!}$.
A: First let $k \geq n$, since there will be no one-to-one functions otherwise.
For the first element of $A$, there are $k$ possibilities for its image under the function (just choose any element of $B$).
For the second element of $A$, there are only $k-1$ possibilities for its image. This is because we can choose any element of $B$ except the element chosen in the first step (choosing the same element again would violate one-to-oneness).
Continue in this way until you reach the final (i.e. $n$th) element of $A$. There are $k - (n - 1) = k - n + 1$ possibilities for its image, since we again must choose some element of $B$ that has not been used in the previous $n-1$ steps.
To get the total number of one-to-one functions, we multiply the number of possibilities we have at each stage (this technique is sometimes known as the Rule of Product). We get
$$
k(k-1)(k-2) \cdots (k - n + 1)
$$
one-to-one functions. This can be written more concisely as
$$
\frac{k!}{(k-n)!}.
$$
