La notación !n y sus propiedades.
El subfactorial de un entero no negativo $n$, que escribimos como $!n$ (o a veces $D_n$), representa el número de desarreglos de un conjunto de $n$ elementos. Un desarreglo es un tipo específico de permutación $\sigma$ del conjunto ${1, 2, \dots, n}$ tal que ningún elemento aparece en su posición original; o sea, $\sigma(i) \neq i$ para todo $1 \le i \le n$. En otras palabras, un desarreglo es una permutación sin puntos fijos.
Este concepto es una aplicación fundamental del Principio de Inclusión-Exclusión (PIE). Aparece seguido en problemas de combinatoria que tienen restricciones en las posiciones, como el clásico "Problema de los Sombreros" (donde $n$ personas dejan sus sombreros y los reciben de vuelta al azar de modo que a nadie le toca el suyo) o los intercambios de "Santa Secreto". Mientras que $n!$ cuenta el número total de formas de ordenar $n$ objetos, $!n$ cuenta el subconjunto específico de ordenamientos donde cada objeto se mueve a un lugar nuevo.
Un detalle clave sobre el subfactorial es su comportamiento asintótico. Conforme $n$ aumenta, la probabilidad de que una permutación aleatoria sea un desarreglo se acerca a $1/e$. Por lo tanto, $!n$ es el entero más cercano a $n!/e$. Esta relación conecta estructuras combinatorias discretas con la constante analítica $e$, lo que te permite hacer aproximaciones rápidas y te da una idea de qué tan comunes son los desarreglos dentro del conjunto de todas las permutaciones.
1. Fórmula Explícita (vía Inclusión-Exclusión) La expresión cerrada para el subfactorial es: $$!n = n! \sum_{k=0}^n \frac{(-1)^k}{k!} = n! \left( \frac{1}{0!} - \frac{1}{1!} + \frac{1}{2!} - \dots + \frac{(-1)^n}{n!} \right)$$
2. Relaciones de Recurrencia Para fines de cálculo, estas recurrencias suelen ser más eficientes: $$!n = (n-1) \left( !(n-1) + !(n-2) \right)$$ $$!n = n \cdot !(n-1) + (-1)^n$$ Casos base: $!0 = 1$ y $!1 = 0$.
3. Fórmula del Entero más Cercano Para $n \ge 1$, puedes calcular $!n$ usando la función piso y el número de Euler $e$: $$!n = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor$$
Teorema: El número de desarreglos de $n$ elementos está dado por $!n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}$.
Demostración: Para la demostración, usa el Principio de Inclusión-Exclusión (PIE).
Sea $S$ el conjunto de todas las permutaciones de ${1, 2, \dots, n}$. El tamaño del universo es $|S| = n!$. Define un conjunto de propiedades $P_1, P_2, \dots, P_n$, donde