# Counting Relation Functions

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$?

-
These are the derangements. Please see the Wikipedia article. – André Nicolas Feb 18 '14 at 2:18

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$

-