Is there a way to solve it by using exclusion-inclusion method

Question

How many functions $f:\{1,2,3 \cdots n\} \rightarrow \{1,2,3 \cdots n\}$ have no fixed points? Is there a way to solve it by using exclusion-inclusion method?

Answer 1

Huh... Exclusion-inclusion principle can be used, but it is a very convoluted way to get to the solution that is actually very simple...

So... applying exclusion-inclusion principle... from all functions take away those that fix 1, 2,... n, then add those that fix pairs etc. - you end up with:

$$n^n-\sum_{k=1}^n (-1)^{k-1}{n \choose k}n^{n-k} $$

which is:

$$n^n+\sum_{k=1}^n (-1)^k{n \choose k}n^{n-k} $$

i.e.

$$\sum_{k=0}^n (-1)^k{n \choose k}n^{n-k} = (n-1)^n$$

And, of course, this is correct by a simple combinatorial argument. (for $f (k) $ you have $n-1$ choices - any number but $k $).