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
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.