Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
2  
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

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.