- $k!$
- $k^2$
- $k^k$
- $2^k$
- $2^{k+1}$

So the question is: how many unique functions can we create by changing the numbers in the tuples? Well, we know the function is one to one, so we know that if our function was {(1, x), (2, y), (3, z)}, x, y, and z have to be different. If we take our example function and choose in the order x, y, z, there are 3 choices for x (out of {1, 2, 3}), 2 choices for y (out of {1, 3}) and only one choice for z (only {1} is left). So the total number of possible functions we could have had is: $3!=3\cdot2\cdot1=6.$ Thus, for a non-empty finite set with $k$ elements, then the number of one-to-one functions from $S$ onto $S$ is $k!$.

**What if we didn't require the functions to be one-to-one? Which of the answers would it be?**

## 7 comments:

## Post a Comment

This webpage is LaTeX enabled. To type in-line formulae, type your stuff between two '$'. To type centred formulae, type '\[' at the beginning of your formula and '\]' at the end.

I think.

It is k^k if we lose the requirement of injectivity. Each of the k elements of S can be mapped to any element of S, of which there are k.

Yes, they would be. Any one to one function would automatically be onto.

Just to qualify a bit more carefully -- any one-to-one function

on a finite setis automatically ontoRight. I was thinking in the context of this question, but it never hurts to be too precise.

Thanks!

Post a Comment