¿De cuántas maneras podemos organizar los ocho dígitos 1,2,3 4,1,2,3,4 para que no haya dos dígitos idénticos adyacentes?

Answer 1

Hay al menos dos formas de hacer esto, pero ambas usan la inclusión-exclusión de una forma u otra, por lo que optaré por la que sea más fácil de explicar.

Primero considere el conjunto [math] \ xi [/ math] de todos los arreglos de [math] 1,1,2,2,3,3,4,4 [/ math]. El tamaño de este conjunto es solo el coeficiente multinomial

[matemáticas] | \ xi | = \ dfrac {8!} {2! ^ 4} \ tag * {} [/ matemáticas]

dado que hay [math] 8! [/ math] arreglos de [math] 8 [/ math] objetos distintos pero luego contamos los duplicados dividiendo por [math] 2! [/ math] Para cada uno de los [math] 4 [/ matemáticas] pares idénticos.

Luego considere los conjuntos [matemáticos] A_i [/ ​​matemáticos] ([matemáticos] i \ in \ {1,2,3,4 \} [/ matemáticos]) de arreglos de dígitos [matemáticos] 1,1,2,2, 3,3,4,4 [/ math] que tienen el par de dígitos [math] i, i [/ math] adyacentes. Podemos contarlos tratando el par de dígitos como un solo objeto [math] \ {ii \} [/ math] y luego contando los arreglos de [math] 1,1, \ ldots, \ {ii \}, \ ldots, 4, 4 [/ matemáticas]. Entonces ahora tenemos [math] 7 [/ math] objetos con [math] 3 [/ math] pares idénticos, por lo tanto

[matemáticas] | A_i | = \ dfrac {7!} {2! ^ 3} \ tag * {} [/ matemáticas]

Luego considere el conjunto de arreglos de [matemáticas] 1,1,2,2,3,3,4,4 [/ matemáticas] que tienen el par de dígitos [matemáticas] i_1, i_1 [/ matemáticas] adyacentes y el par de dígitos [ matemática] i_2, i_2 [/ matemática] adyacente ([matemática] i_1 \ ne i_2 [/ matemática] donde [matemática] i_1, i_2 \ in \ {1,2,3,4 \} [/ matemática]). Esta es la intersección de nuestro primer lote de conjuntos [matemática] A_ {i_1} \ cap A_ {i_2} [/ matemática]. Similar a antes, tratamos [matemáticas] i_1, i_1 [/ matemáticas] como un solo objeto [matemáticas] \ {i_1i_1 \} [/ matemáticas] y [matemáticas] i_2, i_2 [/ matemáticas] como un solo objeto [matemáticas] \ {i_2i_2 \} [/ math], luego organizamos estos [math] 2 [/ math] objetos con los restantes [math] 4 [/ math] dígitos ([math] 2 [/ math] pares de [math] 2 [/ matemáticas] dígitos idénticos) dando

[matemáticas] | A_ {i_1} \ cap A_ {i_2} | = \ dfrac {6!} {2! ^ 2} \ tag * {} [/ matemáticas]

Continuando con este razonamiento para encontrar el tamaño de las intersecciones [matemáticas] 3 [/ matemáticas] y [matemáticas] 4 [/ matemáticas]

[matemáticas] | A_ {i_1} \ cap A_ {i_2} \ cap A_ {i_3} | = \ dfrac {5!} {2!} \ tag * {} [/ matemáticas]

[matemáticas] | A_ {1} \ cap A_ {2} \ cap A_ {3} \ cap A_ {4} | = 4! \ tag * {} [/ math]

Está claro que queremos contar todos los arreglos que no pertenecen a ninguno de los conjuntos [matemática] A_1 [/ matemática] a [matemática] A_4 [/ matemática]. Podemos hacer esto usando el principio de inclusión-exclusión [1] que no probaré aquí, pero si revisas el enlace verás lo sencillo que es.

La declaración del principio para nuestro ejemplo es:

[matemáticas] \ begin {align} | (A_1 \ cup A_2 \ cup A_3 \ cup A_4) ‘| = & | \ xi | – \ dbinom {4} {1} | A_i | + \ dbinom {4} {2} | A_ {i_1} \ cap A_ {i_2} | \\ & – \ dbinom {4} {3} | A_ {i_1} \ cap A_ {i_2} \ cap A_ {i_3} | + \ dbinom {4} {4 } | A_ {1} \ cap A_ {2} \ cap A_ {3} \ cap A_ {4} | \ end {align} \ tag {1} [/ math]

Donde [math] (A_1 \ cup A_2 \ cup A_3 \ cup A_4) ‘[/ math] es el complemento de [math] A_1 \ cup A_2 \ cup A_3 \ cup A_4 [/ math] y, por lo tanto, contiene exactamente los arreglos que quiero contar

Sustituyendo todos los valores relevantes en [matemáticas] (1) [/ matemáticas]

[matemáticas] \ begin {align} | (A_1 \ cup A_2 \ cup A_3 \ cup A_4) ‘| = & \ dfrac {8!} {2! ^ 4} – \ dbinom {4} {1} \ dfrac {7 !} {2! ^ 3} \\ & + \ dbinom {4} {2} \ dfrac {6!} {2! ^ 2} – \ dbinom {4} {3} \ dfrac {5!} {2! } + \ dbinom {4} {4} 4! \ end {align} \ tag * {} [/ math]

[matemáticas] \ implica \ bbox [#FFA, 20px] {| (A_1 \ cup A_2 \ cup A_3 \ cup A_4) ‘| = 864} \ tag {Respuesta} [/ math]

Notas al pie

[1] Principio de inclusión-exclusión – Wikipedia