1. ## Sets and bijections

My Question is

Suppose A is a set with $\left | A \right |=n$
How many functions are there from A to A which are not bijections ?

I don't quite understand how to work this question out.

any help is appreichated

thanks

2. Originally Posted by rpatel
Suppose A is a set with $\left | A \right |=n$
How many functions are there from A to A which are not bijections?
Given a finite set $\left | A \right |=n$ then there are $n!$ bijections from A to A.
There are $n^n$ functions from A to A.

3. Can you answer how many functions there are from A to A which *are* bijections?

4. oops, fixed.

5. ok so this is the answer $n^{n}-n!$

thanks

6. Do you understand how Plato got those numbers?

To construct a function from A to A, we have to map each member of A into something in A. For each member of A, then, we could choose each of the n members of A to map into. There are, of course, "n" ways to do that. Since there are n members of A, and we have n choices for each, by the "fundamental counting principle" we multiply each n by all the others: n multiplied by itself n times is $n^n$.

Now, if a function from A to itself (or from one set to another of the same cardinality) is injective (one to one) it is also surjective (onto) and so a bijection. To construct an injective function from A to A, we choose a single member of A and then can choose any of the n members of A to map it to. There are n ways to do that. Now choose a second member of A. We can map it to any member of A except the one we just mapped the first member into. There are n-1 ways to do that. Now choose a third member of A. We can map it into any member of A except the first two. There are n-2 ways to do that. Continue that way through all members of A. We see that there are $n(n-1)(n-2)\cdot\cdot\cdot 3(2)(1)= n!$ ways to do that.

7. thank you for the explanation. I understand my question now.