Pregunta sobre el principio de inclusión exclusión

Question

¿De cuántas maneras podemos sentar a 3 pares de hermanos en una fila de 7 sillas de manera que nadie se siente al lado de su hermano? [Una silla estará vacía]

Tengo que hay $7!$ formas de sentar a todo el mundo sin restricciones. Hay $2 \cdot 6!$ formas para que cada pareja de hermanos se siente junta, y como hay $3$ hermanos, hay $2 \cdot 3 \cdot 6!$ para que al menos una pareja de hermanos se siente junta.

Así, he conseguido que haya $7! - 6 \cdot 6!$ formas en las que nadie se sienta al lado de sus hermanos.

---

Sin embargo, parece que esta respuesta es incorrecta y hay que sumar el número de asientos con dos parejas sentadas juntas, y luego restar el número de formas de tener cada par de hermanos sentados juntos.

¿Cuál es la razón para hacer esto? No veo por qué hay que volver a sumar el número de plazas con dos de las parejas sentadas juntas.

Answer 1

Supongamos que tenemos seis personas $$a_1,a_2,b_1,b_2,c_1,c_2$$ y una fila de siete sillas. Considere $U$ como el conjunto de todas las formas de sentar a todo el mundo sin restricciones. Considere $A$ como el conjunto de todas las formas de sentarse s.t. $a_1$ y $a_2$ son adyacentes. Consideremos el conjunto $B$ de la misma manera para $b_i$ y el conjunto $C$ para $c_i$ 's. En esta pregunta buscamos el tamaño del conjunto $$A^c\cap B^c\cap C^c$$ pero $$\begin{align*} |A^c\cap B^c\cap C^c|& =|(A\cup B\cup C)^c| \\ &= |U|-|A\cup B\cup C| \end{align*}$$ y $$\begin{align*} |A\cup B\cup C|=& |A|+|B|+|C| \\ &-|A\cap B|-|A\cap C| -|B\cap C| \\ & +|A\cap B\cap C| \\ =& 3\times 2\cdot6! \\ &-3\times2\cdot 2\cdot 5! \\ &+2\cdot 2\cdot2\cdot 4! \end{align*}$$ por lo que la respuesta final es $$7!-6\cdot6!+2\cdot6!-8\cdot4!=3\cdot6!-8\cdot4!=82\cdot4!=82\cdot24=1968.$$

---

Vale, ya veo cuál es el problema. Usas la igualdad $$|A\cup B\cup C|= |A|+|B|+|C|,$$ pero hay que tener en cuenta que esta igualdad sólo se mantiene si $$A\cap B=A\cap C=B\cap C=\emptyset,$$ y eso mi amigo no es cierto aquí; estas intersecciones en nuestro problema específico no están vacías, y eso hace que el problema sea un poco complicado porque por ejemplo cuando se agrega $|A|$ y $|B|$ se cuenta el tamaño de la intersección 2 veces una vez en $|A|$ y una vez en $|B|$ Por lo tanto, es razonable restarlo una vez, y ésa es la idea que subyace al "Principio de Inclusión y Exclusión": hay que "Incluir" cada caso propio sólo una vez, y el recuento adicional debe ser "Excluido". Espero que te ayude a entender mejor la idea.