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

Artículo de la Enciclopedia Libre Universal en Español.

Saltar a navegación, buscar
Un ejemplo sencillo: cardinal de una unión de dos conjuntos

Índice

[escribe] 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)


[escribe] Caso general

[escribe] 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}

[escribe] 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.

[escribe] 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 Ai 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.

[escribe] Referencias

Bibliografía
Autor: M.Romero Schmidtke

Notas

Obtenido de «http://enciclopedia.us.es/index.php/Cardinal_de_una_uni%C3%B3n_de_conjuntos»
Herramientas personales
Espacios de nombres
Variantes
Acciones
Navegación
Herramientas
Crear un libro