4

I have a set $S = \{ 1,2,3,4,5,6,7 \} $

I know that the number of bijective functions $S\rightarrow S$ without any restrictions is $7!$, but how can I count the number of bijective functions $ \phi : S \rightarrow S$ such that $\phi (x) \not= x$ for all $x \in S$?

theta
  • 189

1 Answers1

4

This is the same as the number of derrangements between sets of size 7. Also know as 7 subfactorial denoted $!7$

derrangements do not have a nice closed formula, however they do obey the recurrence relation

$!n=(n-1)(!(n-1)+!(n-2))$

the first $7$ values are $0,1,2,9,44,265,1854$. So $!7=1854$

Asinomás
  • 105,651