Funciones de relación de conteo

Question

Tengo un conjunto$S = \{ 1,2,3,4,5,6,7 \} $

Sé que la cantidad de funciones biyectivas$S\rightarrow S$ sin ninguna restricción es$7!$, pero ¿cómo puedo contar la cantidad de funciones biyectivas$ \phi : S \rightarrow S$ de manera tal que$\phi (x) \not= x$ para todas las$x \in S$?

Answer 1

Este es el mismo que el número de desajustes entre conjuntos de tamaño 7. También se conoce como 7 subfactorial denotado$!7$

los desajustes no tienen una fórmula cerrada agradable, sin embargo obedecen la relación de recurrencia

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

Los primeros valores de$7$ son$0,1,2,9,44,265,1854$. Asi que $!7=1854$