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|.\]
Esto lo podemos generalizar. 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}\]
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\rfloor \qquad {\mbox{para }}n\geq 1}\]
donde \(\lfloor \,\rfloor \) denota la función parte entera más cercana.
Imaginemos que ahora pretendemos dejar fijo \(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 número será:
\[R(n,k)=\binom{n}{k}\,!(n-k)\]
Para vuestra ayuda consultar Derangement.
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. \]
Ejercicios de Repaso
Ejercicio: ¿Cuál es el valor de \(\left\{{\begin{matrix}4\\2\end{matrix}}\right\}+\left\{{\begin{matrix}5\\2\end{matrix}}\right\}\)? |
Ejercicio: ¿Cuántos desarreglos hay en \(S_6\)? |
Ejercicio: ¿Cuántos enteros entre 1 y 105 inclusive no son divisibles por ninguno de los enteros 3, 5, 7? |
Ejercicio: ¿Cuántas palabras de 4 letras pueden formarse usando las letras A, B, C, D, E si debe aparecer al menos una vocal? |
Ejercicio: ¿Cuál es el valor de \(B_5-B_4\)? |