2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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 $... $\endgroup$ – user491874 Dec 27 '17 at 14:34
  • $\begingroup$ first I try to use inclusion/exclusion method to solve the problem just like Derangement problem does $\endgroup$ – Bruce Dec 27 '17 at 14:51
  • $\begingroup$ 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. $\endgroup$ – user491874 Dec 27 '17 at 14:54
  • $\begingroup$ $$ n^n-{n \choose 1}(n-1)^{n-1}+{n \choose 2}(n-2)^{n-2}-\cdots \pm {n \choose n} $$ $\endgroup$ – Bruce Dec 27 '17 at 15:02
  • $\begingroup$ Why $(n-1)^{n-1} $, for instance? Isn't it $n^{n-1} $? (You don't care where the other elements go.) $\endgroup$ – user491874 Dec 27 '17 at 15:17
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Great solution +1 $\endgroup$ – Aqua Dec 27 '17 at 16:18
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.