Cardinal de una unión de conjuntos

Un ejemplo sencillo: cardinal de una unión de dos conjuntos

Introducción con ejemplos

Sean A₁, A₂, A₃ ... A_n 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 A₁, A₂, A₃ ... A_n 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, (A₁, A₂, A₃ ... A_n) y añadamos uno más en la unión: A_n+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 #A_n+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 A_i.

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 A_i, 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

Bibliografía
Autor: M.Romero Schmidtke

Notas