¿Cuántas permutaciones de $\{1,2,.....n\}$ estropear los números impares?

Question

¿Cuántas permutaciones de $\{1,2, \dots , n\}$ estropear los números impares? Tengo la respuesta en mi libro de texto, pero no sé cómo lo consiguieron.

Answer 1

En otras palabras, si $\pi$ es la permutación desea $\pi(n) \ne n$ para todos los impares $n$.
Usted puede hacer esto mediante la inclusión-exclusión. Para cualquier subconjunto $A \subseteq \{1,2,\ldots n\}$, vamos a $f(A)$ el número de permutaciones $\pi$ tal que $\pi(n) = n$ $n \in A$ (y posiblemente otros). Obviamente $f(A) = (n - |A|)!$. Deje $B$ ser cualquier subconjunto de a $\{1,\ldots,n\}$. A continuación, inclusión-exclusión, dice que el número de permutaciones de $\{1,2,\ldots n\}$, con al menos un punto fijo en $B$ es la suma de $(-1)^{|A|-1} f(A)$ sobre todos los subconjuntos de a$A$$B$, es decir, $\displaystyle \sum_{k=1}^{|B|} (-1)^{k-1} (n-k)! {|B| \choose k}$. Reste esta de $n!$ para obtener el número de permutaciones con ningún punto fijo en $B$.

Ver también https://oeis.org/A161131