El principio de inclusión y exclusión: ¿Cuántas permutaciones del conjunto $\{1, 2,. . . , 8\}$ no dejan ningún número par en su lugar?

Question

Tengo que resolver el siguiente problema:

¿Cuántas permutaciones del conjunto $\{1, 2,. . . , 8\}$ no dejan ningún número par en su lugar?

Lo que he probado:

$$8!-\left ( \binom{8}{1}7!-\binom{8}{ 2}6!+\binom{8}{3}5!-\binom{8}{4}4! \right )$$

Pero sé que esto es incorrecto.

¿Puede alguien decirme por qué?

Answer 1

Dejemos que $A_k$ sea el número de permutaciones que fijan el $2k$ -enésimo elemento. Por Inclusión-Exclusión, $$|A_1\cup A_2\cup A_3\cup A_4|=\sum_{1\leq w\leq4}|A_w|- \sum_{1\leq w<x\leq4}|A_w\cap A_x| +\sum_{1\leq w<x<y\leq4}|A_w\cap A_x\cap A_y|- \sum_{1\leq w<x<y<z\leq4}|A_w\cap A_x\cap A_y\cap A_z|$$ $$=\binom{4}{1}\cdot 7!-\binom{4}{2}\cdot 6!+\binom{4}{3}\cdot 5!-\binom{4}{4}\cdot4!=16296.$$ Esto cuenta el número de permutaciones que fijan al menos uno de los elementos pares, por lo que nuestra respuesta final es $8!-16296=24024$ .

Answer 2

Dejemos que $S_j$ sea el conjunto de arreglos con $2j$ se deja en su lugar. A continuación, $$ N_k=\overbrace{\ \ \ \binom{n}{k}\ \ \ }^{\substack{\text{number of}\\\text{ways to pick}\\\text{the $ k $ fixed}\\\text{numbers}}}\overbrace{\vphantom{\binom{n}{k}}(2n-k)!}^{\substack{\text{arrangements}\\\text{of the}\\\text{remaining}\\\text{numbers}}} $$ Según la Principio de inclusión-exclusión generalizado el número de arreglos en ninguno de los $S_j$ es $$ \sum_{k=0}^n(-1)^kN_k $$ para $n=4$ Esto da como resultado $$ \binom{4}{0}8!-\binom{4}{1}7!+\binom{4}{2}6!-\binom{4}{3}5!+\binom{4}{4}4!=24024 $$