¿De cuántas maneras diferentes se pueden permutar los enteros 1 a 9 de modo que ningún entero impar esté en su posición natural?

Answer 1

Esto implica el “principio de inclusión y exclusión” un poco complicado (ver Principio de inclusión-exclusión – Wikipedia).

Tenemos [math] 9! [/ Math] posibles permutaciones sin ninguna restricción.

Debemos excluir las permutaciones donde un número impar está en su posición natural. Hay cinco números impares, por lo que debemos excluir [math] {5 \ choose 1} \ times 8! [/ Math] permutaciones donde un número impar está en su posición natural.

Sin embargo, esta exclusión es demasiado generosa y la exclusión múltiple excluye algunas permutaciones. Agregamos esos nuevamente al considerar todas las permutaciones en las que dos de los cinco números impares están en sus posiciones naturales. Hay [matemáticas] {5 \ elegir 2} \ veces 7! [/ Matemáticas] de estos.

Pero esta inclusión también es demasiado generosa y debemos continuar de esta manera hasta que finalmente consideremos las permutaciones donde todos los números impares están en sus posiciones naturales.

El resultado está dado por:

[matemáticas] \ quad n = {5 \ elegir 0} 9! – {5 \ elegir 1} 8! + {5 \ elegir 2} 7! – {5 \ elegir 3} 6! + {5 \ elegir 4} 5 ! – {5 \ elige 5} 4! [/ Matemáticas]

[matemáticas] \ quad \ quad = 1 \ cdot 9! -5 \ cdot 8! +10 \ cdot 7! -10 \ cdot 6! +5 \ cdot 5! -1 \ cdot 4! [/ math]

[math] \ quad \ quad = 205056 \ [/ math] permutaciones en total.

---

EDITAR: Nunca confío completamente en mí mismo para obtener el principio de inclusión y exclusión correcto. No lo uso a menudo y es una pequeña bestia engañosa.

Para descansar, escribí un pequeño programa (C #) para enumerar las permutaciones válidas y contarlas por fuerza bruta. Afortunadamente, la salida está de acuerdo con mi respuesta.

Permisos nulos ()
{
int [] perm = nuevo int [10];
int n = 0;
PermsRecursive (perm, 1, ref n);
Debug.Print (“Total = {0}”, n);
}

nulo PermsRecursive (int [] perm, int digit, ref int n)
{
if (dígito> 9)
n ++;
más
para (int pos = 1; pos <10; pos ++)
if (perm [pos] == 0 && (pos% 2 == 0 || pos! = dígito))
{
perm [pos] = dígito;
PermsRecursive (perm, dígito + 1, ref n);
perm [pos] = 0;
}
}

La salida fue: Total = 205056