La Enciclopedia Libre Universal en Español dispone de una lista de distribución pública, enciclo@listas.us.es

Cardinal de una unión de conjuntos

De la Enciclopedia Libre Universal en Español
Saltar a: navegación, buscar
Un ejemplo sencillo: cardinal de una unión de dos conjuntos

Introducción con ejemplos

Sean A1, A2, A3 ... An conjuntos. Conociendo el cardinal de cada conjunto, así como el cardinal de cada intersección de dos, tres ... n conjuntos, se quiere hallar una fórmula para calcular el cardinal de la unión .

En ciertos lugares del planeta, esta fórmula se conoce bajo el nombre de fórmula de la criba o principio de la criba. Sin embargo la apelación más conocida es principio de inclusión-exclusión. La vamos a descubrir generalizando a partir de la unión de dos y luego de tres conjuntos.

Sean A y B dos conjuntos, de intersección A ∩ B (en verde en la figura). Para contar todos los elementos de la unión A ∪ B, primero contamos los de A (en amarillo y verde en la figura), luego los de B (en azul y verde) y sumamos los dos números. Pero ... los elementos de la intersección han sido contados dos veces. Entonces tenemos que restar a la suma el cardinal de la intersectión, #(A ∩ B).
La fórmula es por lo tanto:

Diagrama en el caso de tres eventos probabilísticos

Se puede remplazar el cardinal por otra medida de conjuntos, por ejemplo por una probabilidad, si A y B son eventos probabilísticos:

Consideremos ahora un tercer conjunto C, que interseca los dos primeros.
Sumamos primero todo lo que hay en A, B y C separadamente.
Al hacerlo, contamos dos veces los elementos de A ∩ B, B ∩ C y C ∩ A.
Luego debemos restar estos tres conjuntos.
Pero los elementos de A ∩ B ∩ C han sido contados tres veces y restados otras tantas, por lo que tenemos que contabilizarlos de nuevo.
La fórmula es por tanto :


Caso general

Fórmula

La fórmula general, con los conjuntos A1, A2, A3 ... An es:  

Una escritura más rigurosa aunque menos legible es:

      

Finalmente, si se renuncia a reunir las intersecciones que involucran el mismo número de conjuntos, se obtiene la fórmula siguiente, más sencilla y abstracta:

      

Como anteriormente dicho, este teorema se generaliza a cualquier medida m de un espacio métrico, o cualquier probabilidad p:

Prueba

Se puede demostrar esta fórmula por inducción sobre el número de conjuntos involucrados. Para dos y tres es cierta por construcción; también lo es para uno y cero conjunto si se mira atentamente (recordando que la sumas de ningún elemento es el neutro de la adición, es decir cero, y que una unión de ningún conjunto es el neutro por la aplicación «unión» es decir el conjunto vacío).
Supongamos la fórmula cierta para n conjuntos, (A1, A2, A3 ... An) y añadamos uno más en la unión: An+1.

Pongamos
y apliquemos la fórmula para 


La primera suma corresponde a los , el término #An+1 corresponde a I = {n+1}, y la última suma se reescribe:


con I' = I ∪ {n +1} ( #I' = #I + 1; -(-1)#I + 1 = (-1)#I' + 1 ), y corresponde, cuando I' se renombra en I, a los I que contienen a n + 1 y otro(s) elemento(s).

Reuniendo los tres casos anteriores - I no contiene n + 1, I contiene solamente n + 1 , I contiene n + 1 y algo más - se obtiene la suma sobre todos los es decir , que es la fórmula para n + 1 lo que termina la inducción.

Aplicación

He aquí un problema clásico de combinatoria: «Varios caballeros invitados a una reunión dejan en el vestíbulo sendos sombreros. Al terminar esta, un corte de luz les impiden distinguir los sombreros, y cada uno se lleva uno al azar. ¿Cuál es la probabilidad que ningún caballero se quede con el suyo?»

La respuesta depende obviamente del número n de caballeros. En términos matemáticos, se han permutado los sombreros, y se quiere contar el número de permutaciones sin punto fijo, es decir tal que (las personas son numeradas de 1 a n, σ(i) = j significa que la persona i se ha llevado el sombrero de la persona j).

Sean el conjunto de las permutaciones que dejan el número i fijo.

El número de permutaciones de n elementos es , la factorial de n.

(i siendo fijo, quedan n - 1 elementos que pueden permutar libremente entre si).

Con i ≠ j,   (i e j fijos, n - 2 elementos permutan libremente), y más generalmente, la intersección de k conjuntos distintos tiene como cardinal (n - k)!

Formalmente: Con #I = k,
. Además hay intersecciones de k conjuntos distintos Ai.

Entonces la formula da

Las permutaciones que no contienen puntos fijos son las que no pertenecen a la unión de los Ai, luego están en el conjunto complementario, cuyo cardinal es: .

La probabilidad se obtiene dividiendo el cardinal calculado por el del conjunto entero de las permutaciones:

Esta suma es una suma parcial de una serie exponencial, que converge muy rapidamente hacia , donde e ≈ 2,7182818285 es la base de los logaritmos neperianos.

Referencias

Bibliografía
Autor: M.Romero Schmidtke

Notas