4
$\begingroup$

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

  • 0
    yes I mean one to one functions :) sorry im tired :)2011-08-20

2 Answers 2

5

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

4

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