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)

Printable View

- Dec 28th 2009, 09:04 AMrpatelSets 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 AMPlato
- Dec 28th 2009, 09:15 AMDefunkt
Can you answer how many functions there are from A to A which *are* bijections?

- Dec 28th 2009, 09:29 AMDefunkt
oops, fixed.

- Dec 28th 2009, 10:51 AMrpatel
ok so this is the answer $\displaystyle n^{n}-n!$

thanks - Dec 29th 2009, 03:48 AMHallsofIvy
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 AMrpatel
thank you for the explanation. I understand my question now.(Happy)