amount of one to one functions of two sets of cardinalities $n,k$

Question

I have a homework question I have been struggling with which is:

How many one to one sets are there from $A$ to $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

Answer 1

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)!}$.

Answer 2

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 (since this 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)!}. $$