5.1: El tamaño de una unión de conjuntos
- Page ID
- 112573
Uno de nuestros primeros principios de conteo fue el principio de suma que dice que el tamaño de una unión de conjuntos disjuntos es la suma de sus tamaños. Calcular el tamaño de los conjuntos superpuestos requiere, naturalmente, información sobre cómo se superponen. Tomar en cuenta dicha información nos permitirá desarrollar una poderosa extensión del principio de suma conocido como el “principio de inclusión y exclusión”.
5.1.1: Uniones de Dos o Tres Juegos
\(\circ\) Exercise \(225\)
En un estudio de laboratorio de biología sobre los efectos de los ingredientes fertilizantes básicos en\(16\) las plantas, las plantas se tratan con potasa,\(16\) las plantas se tratan con fosfato, y entre estas plantas, ocho se tratan con fosfato y potasa. No se utilizan otros tratamientos. ¿Cuántas plantas reciben al menos un tratamiento? Si se estudian\(32\) plantas, ¿cuántas no reciben tratamiento?
\(+\) Exercise \(226\)
Dar una fórmula para el tamaño de la unión\(A ∪ B\) de dos juegos\(A\) y\(B\) en términos de los tamaños\(|A|\) de\(A\),\(|B|\) de\(B\), y\(|A ∩ B|\) de\(A ∩ B\). Si\(A\) y\(B\) son subconjuntos de algún conjunto “universal”\(U\), expresar el tamaño del complemento\(U − (A ∪ B)\) en términos de los tamaños\(|U|\) de\(U\),\(|A|\) de\(A\)\(B\),\(|B|\) de y\(|A ∩ B|\) de\(A ∩ B\). (Pista).
\(\circ\) Exercise \(227\)
En el Problema 225, solo había dos fertilizantes utilizados para tratar las plantas de muestra. Ahora supongamos que hay tres tratamientos con fertilizantes, y\(15\) las plantas se tratan con nitratos,\(16\) con potasa,\(16\) con fosfato,\(7\) con nitrato y potasa,\(9\) con nitrato y fosfato,\(8\) con potasa y fosfato y\(4\) con los tres. Ahora, ¿cuántas plantas han sido tratadas? Si se estudiaban\(32\) las plantas, ¿cuántas no recibieron ningún tratamiento?
\(\bullet\) Exercise \(228\)
Dar una fórmula para el tamaño de\(A ∪ B ∪ C\) en términos de los tamaños de\(A\),\(B\),\(C\) y las intersecciones de estos conjuntos. (Pista).
5.1.2: Uniones de un número arbitrario de conjuntos
\(\bullet\) Exercise \(229\)
Conjetura una fórmula para el tamaño de una unión de conjuntos
\(A_1 ∪ A_2 ∪ · · · ∪ A_n = A = \bigcup_{i=1}^{n} A_i \)
en cuanto a los tamaños de los conjuntos Ai y sus intersecciones.
No es probable que la dificultad de generalizar el Problema 228 al Problema 229 sea de poder ver cuál es la conjetura correcta, sino de encontrar una buena notación para expresar tu conjetura. De hecho, sería más fácil para algunas personas expresar la conjetura con palabras que expresarla en una notación. Aquí hay algunas anotaciones que facilitarán tu tarea. Definamos
\(\bigcap_{i:i∈I} A_i\)
para significar la intersección sobre todos los elementos\(i\) en el conjunto\(I\) de\(A_i\).
Así
\[ \bigcap_{i:i∈{1,3,4,6}} = A_1 ∩ A_3 ∩ A_4 ∩ A_6. \label{5.1.1}\]
Este tipo de notación, que consiste en un operador con una descripción debajo de los valores de una variable ficticia de interés para nosotros, se puede extender de muchas maneras. Por ejemplo,
\[\bigcap_{I:I⊆{1,2,3,4}, |I|=2} | ∩_{i∈I} A_i | = |A_1 ∩ A_2| + |A_1 ∩ A_3| + |A_1 ∩ A_4| + |A_2 ∩ A_3| + |A_2 ∩ A_4| + |A_3 ∩ A_4|. \label{5.1.2}\]
\(\bullet\) Exercise \(230\)
Usa notación algo así como la de Ecuación\ ref {5.1.1} y Ecuación\ ref {5.1.2} para expresar la respuesta al Problema 229. Tenga en cuenta que hay muchas formas correctas diferentes de hacer este problema. Intenta anotar más de uno y elige el más bonito que puedas. Di por qué la elegiste (porque tu visión de lo que hace que una fórmula sea agradable puede ser diferente de la de otra persona). La fórmula más bonita no necesariamente involucrará todos los elementos de Ecuaciones\ ref {5.1.1} y\ ref {5.1.2}. (La versión del autor no utiliza todos esos elementos.
\(\bullet\) Exercise \(231\)
Un grupo de\(n\) alumnos va a un restaurante llevando mochilas. El encargado invita a todos a revisar su mochila en el mostrador de control y todos lo hacen. Mientras están comiendo, un niño que juega en la sala de cheques se mueve aleatoriamente alrededor de los talones de cheque de reclamo en las mochilas. Intentaremos calcular la probabilidad de que, al final de la comida, al menos un alumno reciba su propia mochila. Esta probabilidad es la fracción del número total de formas de devolver las mochilas en las que al menos un estudiante recupera su propia mochila.
a) ¿Cuál es el número total de formas de devolver las mochilas?
b) ¿En cuántas de las distribuciones de mochilas a los alumnos al menos un alumno obtiene su propia mochila? (Pista: Para cada alumno, ¿qué tan grande es el conjunto de distribuciones de mochilas en las que ese alumno obtiene la mochila correcta? Podría ser una buena idea considerar primero casos con\(n = 3\),\(4\), y\(5\).) (Pista).
(c) ¿Cuál es la probabilidad de que al menos un alumno obtenga la mochila correcta?
d) ¿Cuál es la probabilidad de que ningún estudiante obtenga su propia mochila?
\(\rightarrow\)e) A medida que aumenta el número de alumnos, ¿cuál es la probabilidad de que ningún alumno obtenga la mochila correcta?
El problema 231 se llama “clásicamente” el problema del hatcheck; el nombre proviene de sustituir sombreros por mochilas. También a veces se le llama el problema del desajuste. Un desajuste de un conjunto\(n\) de elementos es una permutación de ese conjunto (pensado como una bijección) que no mapea ningún elemento del conjunto a sí mismo. Se puede pensar en una forma de devolver las mochilas como una permutación\(f\) de los alumnos:\(f(i)\) es el dueño de la mochila que\(i\) recibe el alumno. Entonces un desconcierto es una manera de devolver las mochilas para que ningún estudiante obtenga las suyas propias.
5.1.3: El principio de inclusión y exclusión
La fórmula que has dado en el Problema 230 suele llamarse el principio de inclusión y exclusión para uniones de conjuntos. El motivo es el patrón en el que la fórmula primero agrega (incluye) todos los tamaños de los conjuntos, luego resta (excluye) todos los tamaños de las intersecciones de dos conjuntos, luego agrega (incluye) todos los tamaños de las intersecciones de tres conjuntos, y así sucesivamente. Observe que aún no hemos probado el principio. Hay una variedad de pruebas. Quizás una de las más directas (aunque no la más elegante) es una prueba inductiva que se basa en el hecho de que
\[A_1 ∪ A_2 ∪ · · · ∪ A_n = (A_1 ∪ A_2 ∪ · · · ∪ A_{n−1}) ∪ A_n\]
y la fórmula para el tamaño de una unión de dos juegos.
Ejercicio\(232\)
Dé una prueba de su fórmula para el principio de inclusión y exclusión. (Pista).
Ejercicio\(233\)
Obtenemos una prueba más elegante si pedimos un enumerador de imágenes para\(A_1 ∪ A_2 ∪ · · · ∪ A_n\). Así que supongamos que\(A\) es un conjunto con una función de imagen\(P\) definida en él y que cada conjunto\(A_i\) es un subconjunto de\(A\).
a. pensando en cómo obtuvimos la fórmula para el tamaño de una unión, escriba en su lugar una conjetura para el enumerador de imágenes de un sindicato. Podría usar una notación como\(E_P ( \bigcap_{i:i∈S} A_i)\) para el enumerador de imágenes de la intersección de los conjuntos\(A_i\) para\(i\) en un subconjunto\(S\) de\([n]\).
b. Si\(x ∈ \bigcup_{i=1}^{n} A_i\), ¿cuál es el coeficiente de\(P(x)\) en (el lado inclusión-exclusión de) su fórmula para\(E_P ( \bigcup_{i=1}^{n} A_i)\)? (Pista).
c. Si\(x \notin \bigcup_{i=1}^{n} A_i\) ¿cuál es el coeficiente de\(P(x)\) en (el lado inclusión-exclusión de) su fórmula para\(E_P ( \bigcup_{i=1}^{n} A_i)\)?
d. ¿Cómo ha demostrado su conjetura para el enumerador de cuadros de la unión de los conjuntos\(A_i\)?
e. ¿Cómo se puede obtener la fórmula para el principio de inclusión y exclusión de su fórmula para el enumerador de imágenes de la unión?
Ejercicio\(234\)
Frecuentemente cuando aplicamos el principio de inclusión y exclusión, tendremos una situación como la del Problema 231d. Es decir, vamos a tener un conjunto\(A\) y subconjuntos\(A_1, A_2, . . . , A_n\) y vamos a querer el tamaño o la probabilidad del conjunto de elementos en\(A\) que no están en la unión. Este conjunto se conoce como el complemento de la unión de la\(A_i\) s en\(A\), y se denota por\(A \setminus \bigcup^{n}_{i=1} A_i\), o si\(A\) es claro desde el contexto, por\(\overline{\bigcup^{n}_{i=1} A_i}\). Dar la fórmula para\(\overline{\bigcup^{n}_{i=1} A_i}\). El principio de inclusión y exclusión se refiere generalmente tanto a esta fórmula como a la de la unión.
Podemos encontrar una manera muy elegante de escribir la fórmula en el Problema 234 si lo dejamos\(\bigcap_{i:i∈∅} A_i = A\). Por esta razón, si tenemos una familia de subconjuntos\(A_i\) de un conjunto\(A\), definimos 1\(\bigcap_{i:i∈∅} A_i = A\).