El principio de inclusión-exclusión permite calcular el cardinal de la unión de varios conjuntos, mediante los cardinales de cada uno de ellos y todas sus posibles intersecciones. Si consideramos que tenemos dos conjuntos finitos \(A\) y \(B\), resultará: \[|A \cup B| = |A| + |B| – |A \cap B|.\]
Imaginemos que tenemos tres conjuntos finitos:
\[|A \cup B \cup C| = |A| + |B| + |C| – |A \cap B| – |A \cap C| – |B \cap C| + |A \cap B \cap C|.\]
Ejercicio: En una clase de 1º de Ingeniería Informática con 60 alumnos, se realiza una encuesta sobre los lenguajes de programación que conocen. Los resultados son los siguientes:
- 25 conocen Python.
- 26 conocen Java.
- 18 conocen C++.
- 9 conocen Python y Java.
- 11 conocen Java y C++.
- 7 conocen Python y C++.
- 3 conocen los tres lenguajes.
¿Cuántos alumnos conocen al menos uno de estos tres lenguajes? ¿Cuántos alumnos no conocen ninguno de los tres?
Principio de Inclusión-Exclusión(PIE): Si A1, …, An son conjuntos finitos entonces:
\[\begin{align}\biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right|-\sum_{i,j\,:\,1 \le i < j \le n}\left|A_i\cap A_j\right| \\& {}\qquad +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n+1} \left|A_1\cap\cdots\cap A_n\right|\end{align}\]
Una consecuencia muy práctica es la siguiente.
Si consideramos un conjunto universal $S$ y una serie de subconjuntos $A_i$ (aquellos que cumplen la propiedad $i$), la cantidad de elementos que no cumplen ninguna de las propiedades se expresa como el cardinal de la intersección de sus complementos $\bar{A}_i$.
$$\left| \bigcap_{i=1}^{n} \bar{A}_i \right| = \left| S – \bigcup_{i=1}^{n} A_i \right| = |S| – \sum_{i=1}^{n} |A_i| + \sum_{1 \le i < j \le n} |A_i \cap A_j| - \cdots + (-1)^n |A_1 \cap \cdots \cap A_n|$$ Nota: Esta estructura es la base de algoritmos de conteo en grafos y es vital para entender la complejidad de problemas combinatorios donde el espacio de búsqueda es muy grande.
Ejercicio: Un administrador de sistemas está analizando un lote de 100 peticiones HTTP sospechosas en un servidor. Para limpiar el tráfico, necesita identificar cuántas peticiones son «seguras», es decir, aquellas que no presentan ninguno de los siguientes tres fallos de seguridad:
* Propiedad $A_1$: La petición proviene de una IP en lista negra.
* Propiedad $A_2$: La petición contiene caracteres SQL maliciosos.
* Propiedad $A_3$: La petición supera el tamaño de buffer permitido.Tras un análisis automatizado, se obtienen los siguientes datos:
* $|A_1| = 12$, $|A_2| = 18$, $|A_3| = 15$
* Peticiones con dos fallos: $|A_1 \cap A_2| = 7$, $|A_2 \cap A_3| = 8$, $|A_1 \cap A_3| = 5$
* Peticiones con los tres fallos simultáneos: $|A_1 \cap A_2 \cap A_3| = 2$Utilizando la forma complementaria del Principio de Inclusión-Exclusión, calcula cuántas peticiones son seguras (no tienen ningún fallo).
Nota: Este enfoque es mucho más eficiente cuando programamos filtros. En lugar de intentar identificar cada caso «limpio» por separado, es más sencillo restar del total las ocurrencias de errores conocidos, ajustando las intersecciones para no sobre-contar o infra-contar los casos críticos.
Ejercicio: ¿Cuántos números de 9 cifras tiene, al menos una vez cada uno, los dígitos 1, 3 y 7? Por ejemplo, 123456789, 13777777, 000000137.
Desarreglos
Uno de las aplicaciones de este principio la encontramos en la cuenta de desarreglos.
Consideremos el conjunto de las permutaciones \(S_n\), donde un elemento será de la forma:
\[\displaystyle \left(\begin{array}{cccccccc}1 & 2 & 3 & 4 & 5 \cdots & n\\ \sigma_1 & \sigma_2 & \sigma_3 & \sigma_4 & \sigma_5 \cdots & \sigma_n \end{array}\right) .\]
Siendo \(\sigma_i\in I=\{1,2,3,4,…,n\}\) y de modo que \(\sigma_i\neq \sigma_j\forall i\neq j\).
Hemos visto que \(S_n\) con la operación composición de permutaciones, \(\circ\), le confiere una estructura de grupo; \((S_n,\circ)\) es un grupo.
Definimos un desarreglo como una permutación \(\sigma\in S_n\) talque \(\sigma_i\neq i\forall i\in I\). El Principio de inclusión-exclusión nos ayuda a contar el número de desarreglos que podemos encontrar en el conjunto \(S_n\).
El número de desarreglos de \(n\) elementos también se conoce como subfatorial, a veces escrito como \(!n\), que resulta:
\[{\displaystyle !n=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}.\]
Teniendo en cuenta que el sumatorio anterior se puede expresar como el número \(e\), puede verse que
\[{\displaystyle !n=\left\lfloor {\frac {n!}{e}}\right\rceil \qquad {\mbox{para }}n\geq 1}\]
donde \(\lfloor \,\rceil \) denota la función parte entera más cercana.
Ejercicio: Construye una función en maxima que nos devuelva $D_n$
Ejercicio: Construye una función en maxima que nos devuelva \(D_n\) utilizando
\[{\displaystyle !n=n!\sum _{k=0}^{n}{\frac {(-1)^{k}}{k!}}}.\]
Proposición: Los desarreglos siguen la relación de recurrencia \[D_n = (n-1)(D_{n-1} + D_{n-2}).\]
Ejercicio: Construye una función recursiva en maxima que nos devuelva \(D_n\)
Imaginemos que ahora pretendemos dejar fijos \(k\) elementos y los restantes se desarreglen; es decir, queremos contar el número de permutaciones de \(n\) elementos que dejan fijos \(k\) de ellos. Este era el problema de los encuentros que ya vimos. Sin embargo, ahora lo podemos afrontar mediante desarreglos:
\[T(n,k)=\binom{n}{k}\,!(n-k)\]
Por último, un resultado que podemos obtener aplicando este tema:
Teorema El número de de aplicaciones sobreyectivas diferentes que se pueden establecer de un conjunto \(A\) de cardinal \(n\) en otro conjunto \(B\) de cardinal \(r\) con \(r\leq n\) es \[ \sum_{i=0}^r(-1)^i\binom{r}{i}(r-i)^n. \]
|
Ejercicio: ¿Cuál es el valor de \(B_5-B_4\)? |