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   A_1 \cup A_2 \cup ... \cup A_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:

  \#(A \cup B) = \# A \ + \ \# B \ - \  \# (A \cap B)
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:
  p(A \cup B) = p(A) + p(B) - p(A \cap B)

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 :  \#(A \cup B \cup C) \ =  \   \# A \ \ + \ \ \# B \ \ + \ \ \# C \ \ - \ \ \# (A \cap B) \ \ - \ \ \# (B \cap C) \ \ - \ \ \# (C \cap A) \ \ + \ \ \# (A \cap B \cap C)


Caso general

Fórmula

La fórmula general, con los conjuntos A1, A2, A3 ... An es:  
 \begin{matrix}{ } \\ \# \bigcup A_i \\ { }_{i \in [1;n]}  \end{matrix}  = \sum_{i \in [1;n]} \# A_i \ - \  \sum_{i \ne j} \#(A_i \cap A_j) \ + \ \sum_{i \ne j \ne k \ne i} \#(A_i \cap A_j \cap A_k) \ - ...

Una escritura más rigurosa aunque menos legible es:

    \begin{matrix} { } \\ \# \left ( \bigcup A_i \right ) \\ { }_{i \in [1;n]}  \end{matrix} \ \ = \ \ \sum_{k=1}^n (-1)^{k+1} \sum_{ { }_{\#I=k, I \subseteq [1,n]}} \begin{matrix} { } \\ { } \\ \# \left ( \bigcap A_i \right ) \\ { }_{i \in I } \\ { } \end{matrix}    

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:

    \begin{matrix} { } \\ \# \left ( \bigcup A_i \right )  \\ { }_{i \in [1;n]}  \end{matrix} \ \ = \sum_{\varnothing \ne I \subseteq [1,n] } (-1)^{\# I + 1} \begin{matrix} { } \\ { } \\ \# \left ( \bigcap A_i \right ) \\ { }_{i \in I } \\ { } \end{matrix}    

Como anteriormente dicho, este teorema se generaliza a cualquier medida m de un espacio métrico, o cualquier probabilidad p:
 \begin{matrix} { } \\ p \left ( \bigcup A_i \right ) \\ { }_{i \in [1;n]}  \end{matrix} \ \ = \ \ \sum_{k=1}^n (-1)^{k+1} \sum_{{}_{\#I=k, I \subseteq [1,n]}} \begin{matrix} { } \\ { } \\ p \left ( \bigcap A_i \right ) \\ { }_{i \in I } \\ { } \end{matrix} =  \sum_{\varnothing \ne I \subseteq [1,n] } (-1)^{\# I + 1} \begin{matrix} { } \\ { } \\ p \left ( \bigcap A_i \right ) \\ { }_{i \in I } \\ { } \end{matrix}

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
A = \begin{matrix}{ } \\  \bigcup A_i \\ { }_{i \in [1;n]}  \end{matrix} \ \mbox{ y } \  B= A_{n+1}
y apliquemos la fórmula para  \# (A \cup B):

 \#(A \cup B) = \# A \ \  + \ \  \# B \ \ - \ \  \# (A \cap B) =  \sum_{\varnothing \ne I \subseteq [1,n] } (-1)^{\# I + 1} \begin{matrix} { } \\ { } \\ \# \left ( \bigcap A_i \right ) \\ { }_{i \in I } \\ { } \end{matrix}  \ \ + \ \ \# A_{n+1} \ - \ \sum_{\varnothing \ne I \subseteq [1,n] } (-1)^{\# I + 1} \begin{matrix} { } \\ { } \\ \# \left ( \bigcap A_i \right ) \\ { }_{i \in I } \\ { } \end{matrix} \cap A_{n+1}

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

 - \ \sum_{\varnothing \ne I \subseteq [1,n] } (-1)^{\# I + 1} \begin{matrix} { } \\ { } \\ \# \left ( \bigcap A_i \right ) \\ { }_{i \in I } \\ { } \end{matrix} \cap A_{n+1} = 
\ \sum_{ \{n+1\} \varsubsetneqq I' \subseteq [1,n+1] } (-1)^{\# I' + 1} \begin{matrix} { } \\ { } \\ \# \left ( \bigcap A_i \right ) \\ { }_{i \in I' } \\ { } \end{matrix}

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 I \subseteq [1,n+1] es decir  \sum_{\varnothing \ne I \subseteq [1,n+1] } (-1)^{\# I + 1} \begin{matrix} { } \\ { } \\ \# \left ( \bigcap A_i \right ) \\ { }_{i \in I } \\ { } \end{matrix} , 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  \forall i \in \{1, 2, ... n\} , \sigma (i) \ne i (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 A_i = \{ \sigma \in \mathfrak{S}_n , \sigma(i) = i \} el conjunto de las permutaciones que dejan el número i fijo.

El número de permutaciones de n elementos es \# \mathfrak{S}_n = Card \  \mathfrak{S}_n = n! , la factorial de n.

\# A_i = (n-1)! (i siendo fijo, quedan n - 1 elementos que pueden permutar libremente entre si).

Con i ≠ j,  \# \left (A_i \cap A_j \right ) = (n-2)! (i e j fijos, n - 2 elementos permutan libremente), y más generalmente, la intersección de k conjuntos A_i distintos tiene como cardinal (n - k)!

Formalmente: Con #I = k,
  \begin{matrix}{ } \\ \# \bigcap A_i \\ { }_{i \in I \subseteq [1;n]} \end{matrix} = (n-k)!
. Además hay C_n^k intersecciones de k conjuntos distintos Ai.

Entonces la formula da \begin{matrix} { } \\ \# \left ( \bigcup A_i \right ) \\ { }_{i \in [1;n]}  \end{matrix} \ \ = \ \ \sum_{k=1}^n (-1)^{k+1} \sum_{ { }_{\#I=k, I \subseteq [1,n]}} \begin{matrix} { } \\ { } \\ \# \left ( \bigcap A_i \right ) \\ { }_{i \in I } \\ { } \end{matrix} = \sum_{k=1}^n (-1)^{k+1} C_n^k (n-k)! = \sum_{k=1}^n (-1)^{k+1} \frac {n!} {k! (n-k)!} (n-k)!  = \sum_{k=1}^n (-1)^{k+1} \frac {n!} {k!}

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: \# \left ( \mathfrak{S}_n - { } \begin{matrix} { } \\  \bigcup A_i  \\ { }_{i \in [1;n]}  \end{matrix} \right ) = \# \left ( \mathfrak{S}_n \right ) - \begin{matrix} { } \\ \# \left ( \bigcup A_i \right ) \\ { }_{i \in [1;n]}  \end{matrix} = n! - \sum_{k=1}^n (-1)^{k+1} \frac {n!} {k!} = n! + \sum_{k=1}^n (-1)^k \frac {n!} {k!} = \sum_{k=0}^n (-1)^k \frac {n!} {k!} = n!\sum_{k=0}^n \frac {(-1)^k} {k!}.

La probabilidad se obtiene dividiendo el cardinal calculado por el del conjunto entero de las permutaciones:
p = \frac{ n!\sum_{k=0}^n \frac {(-1)^k} {k!} } {n!} = \sum_{k=0}^n \frac {(-1)^k} {k!}

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

Referencias

Fuentes empleadas y notas

Bibliografía
Autor: M.Romero Schmidtke