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

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?

• What do you get when you try to apply inclusion/exclusion formula? For example, set $A_i$ to be the set of all functions that fix $i$... – user491874 Dec 27 '17 at 14:34
• first I try to use inclusion/exclusion method to solve the problem just like Derangement problem does – Bruce Dec 27 '17 at 14:51
• Yep, can you please update the question with what you have calculated so far and where you are stuck. I guess the sum you get is big and you don't see the way to reduce it - at least we can check if you got that sum right. – user491874 Dec 27 '17 at 14:54
• $$n^n-{n \choose 1}(n-1)^{n-1}+{n \choose 2}(n-2)^{n-2}-\cdots \pm {n \choose n}$$ – Bruce Dec 27 '17 at 15:02
• Why $(n-1)^{n-1}$, for instance? Isn't it $n^{n-1}$? (You don't care where the other elements go.) – user491874 Dec 27 '17 at 15:17

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$).

• Great solution +1 – Aqua Dec 27 '17 at 16:18

From wikipedia, the number of derangement is:

$$n!-{n \choose 1}(n-1)!+{n \choose 2}(n-2)!-\cdots \pm {n \choose n}0! =n!+\sum_{i=1}^n (-1)^i{n \choose i} (n-i)!$$

• $f$ is a function not permutation,so this problem is nto a dearrangemtn problem – Bruce Dec 27 '17 at 14:49
• Ahh, yes. You didn't say it is bijective. Sorry, but perhaps it could give you an idea how to aproach. – Aqua Dec 27 '17 at 14:51