Inclusión-Exclusión y sus diversas Aplicaciones

En el campo de la combinatoria, es un método de conteo utilizado para calcular la cardinalidad del conjunto de unión. De acuerdo con el principio básico de Inclusión-Exclusión :

Para 2 conjuntos finitos $A_1$ y $A_2$ , que son subconjuntos del conjunto Universal, entonces $(A_1-A_2), (A_2-A_1)$ y $(A_1\bigcap A_2)$ son conjuntos disjuntos.

De ahí que se pueda decir que,
$\left|(A_1-A_2)\bigcup(A_2-A_1)\bigcup(A_1\bigcap A_2)\right| = \left|A_1\right| - \left|A_1\bigcap A_2\right| + \left|A_2\right| - \left|A_1\bigcap A_2\right| + \left|A_1\bigcap A_2\right|$

$\left|A_1 \bigcup A_2\right| = \left|A_1\right| + \left|A_2\right| -\left|A_1 \bigcap A_2\right|$ .
Análogamente para 3 conjuntos finitos $A_1$ , $A_2$ y $A_3$ ,
$\left|A_1 \bigcup A_2 \bigcup A_3\right| = \left|A_1\right| + \left|A_2\right| + \left|A_3\right| - \left|A_1 \bigcap A_2\right| - \left|A_2 \bigcap A_3\right| - \left|A_1 \bigcap A_3\right|+ \left|A_1 \bigcap A_2 \bigcap A_3\right|$

Principio :

El principio de inclusión-exclusión dice que para cualquier número de conjuntos finitos $A_1, A_2, A_3... A_i$ , la unión de los conjuntos viene dada por = Suma de los tamaños de todos los conjuntos individuales – Suma de todas las intersecciones de 2 conjuntos + Suma de todas las intersecciones de 3 conjuntos – Suma de los 4 -set intersecciones .. + $(-1)^{i+1}$ Suma de todas las intersecciones i-set.

En general se puede decir que,

$\left|A_1 \bigcup A_2 \bigcup A_3 .. \bigcup A_i\right| = \sum\limits_{1 \leq k \leq i} \left|A_k\right| + (-1)\sum\limits_{1 \leq k_1 \textless k_2 \leq i} \left|A_{k_1} \bigcap A_{k_2}\right| + (-1)^2\sum\limits_{1 \leq k_1 \textless k_2 \textless k_3 \leq i} \left|A_{k_1} \bigcap A_{k_2} \bigcap A_{k_3}\right| .. + (-1)^{i+1}\sum\limits_{1 \leq k_1 \textless k_2 \textless k_3 \textless .. k_i\leq i} \left|A_{k_1} \bigcap A_{k_2} \bigcap A_{k_3} ..\bigcap A_{k_i}\right|$

Propiedades :

Calcula el número total de elementos que satisfacen al menos una de varias propiedades.
Previene el problema de la doble contabilización.

Ejemplo 1:
Como se muestra en el diagrama, se dan 3 conjuntos finitos A, B y C con sus valores correspondientes. Calcular $\left|A \bigcup B \bigcup C\right|$ _

Aplicaciones:

Desordenes
Para determinar el número de desarreglos (o permutaciones) de n objetos tales que ningún objeto está en su posición original (como el problema de la verificación del sombrero).
Como ejemplo podemos considerar los desarreglos del número en los siguientes casos:
Para i = 1, el número total de desarreglos es 0.
Para i = 2, el número total de desarreglos es 1. Esto es $2 1$ .
Para i = 3, el número total de trastornos es 2. Estos son $2 3 1$ y 3 1 2.

Publicación traducida automáticamente

Artículo escrito por Anand_Shekhar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Principio :

Aplicaciones:

Deja una respuesta Cancelar la respuesta