# 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

-
There are $n$ people (set $A$) and $k$ chairs in a row (set $B$). How many ways are there to seat all the people? For concreteness pick $n=5$, $k=9$. One-to-one (injective) means that any chair can have at most one occupant. Comment: The symbols feel strange, usually one chooses notation so that $k \le n$. Here we need $k \ge n$, else the answer is $0$. – André Nicolas Aug 20 '11 at 18:41
yes I mean one to one functions :) sorry im tired :) – Jason Aug 20 '11 at 19:50

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

-

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

-