# Sets and bijections

• Dec 28th 2009, 09:04 AM
rpatel
Sets and bijections
My Question is

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

(Happy)
• Dec 28th 2009, 09:15 AM
Plato
Quote:

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

Given a finite set $\displaystyle \left | A \right |=n$ then there are $\displaystyle n!$ bijections from A to A.
There are $\displaystyle n^n$ functions from A to A.
So what is the answer to your question?
• Dec 28th 2009, 09:15 AM
Defunkt
Can you answer how many functions there are from A to A which *are* bijections?
• Dec 28th 2009, 09:29 AM
Defunkt
oops, fixed.
• Dec 28th 2009, 10:51 AM
rpatel
ok so this is the answer $\displaystyle n^{n}-n!$

thanks
• Dec 29th 2009, 03:48 AM
HallsofIvy
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 $\displaystyle 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 $\displaystyle n(n-1)(n-2)\cdot\cdot\cdot 3(2)(1)= n!$ ways to do that.
• Dec 29th 2009, 04:42 AM
rpatel
thank you for the explanation. I understand my question now.(Happy)