I have this question: Consider the set $S={1,2,...,n}\subset\mathbb{N}$. How many 1-1 and onto functions $f:S\rightarrow S$ can we find such that, for any two of them f and g, we have $f(x)\neq g(x)$ for all $x\in S$?
My take on this is that we start with a pair $f,g$ of functions that satisfy $f(x)\neq g(x)$ for all $x\in S$. We have n options for $f(1)$, and n-1 options for $g(1)$. Similarly we have $n-2$ options for f(2), $n-3$ options for g(2), etc. Is this right?
Also, if this is right, then how do I find the total number of functions? I mean the multiplication principle would imply $n!$ cases. Or do I just add the cases together as in $n(n-1)+(n-2)(n-3)+...$ I'm very confused about this. Why can't Combinatorics sort itself out with good old fashioned clear theorems like Euclidean Geometry?
Clearly there are at most $n$ such functions: were there more it would be impossible for all the $f_i(1)$, say, to be distinct.
Can there be $n$? Sure. Just define $f_i(k)=k+i\pmod n$ (where $0\pmod n$ is understood to be $n$).
Thus, the answer is $n$.