Thread: Sets and bijections

My Question is

Suppose A is a set with
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

Originally Posted by rpatel

Suppose A is a set with
How many functions are there from A to A which are not bijections?

Given a finite set then there are bijections from A to A.
There are functions from A to A.
So what is the answer to your question?

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

oops, fixed.

ok so this is the answer

thanks

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 .

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 ways to do that.

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