Principio de inclusión-exclusión en combinatoria

¿Quién es dueño de qué?

Supongamos que hay un grupo de personas en el que algunos poseen perros, algunos poseen gatos y algunos poseen tanto perros como gatos. Digamos que queremos saber la cantidad de personas que poseen perros o gatos (o ambos). Si simplemente tratamos de sumar la cantidad de personas que poseen perros y la cantidad de personas que poseen gatos, contaremos dos veces a las personas que poseen perros y gatos.

El principio de inclusión-exclusión tiene en cuenta la posibilidad de superposición entre dos (o más) colecciones para que podamos contar con precisión el número de elementos en una colección u otra (o ambas).

Teoría básica de conjuntos

Para explicar el principio de inclusión-exclusión, primero necesitamos cubrir alguna teoría básica de conjuntos. Un conjunto es una colección de elementos relacionados, como dueños de perros o estudiantes en una clase de matemáticas discreta. Un elemento que está contenido en el conjunto se conoce como miembro o elemento del conjunto.

Por ejemplo: si tenemos un conjunto A, el número de elementos en A se denota como | A | y se conoce como la cardinalidad de A. Ahora considere dos conjuntos (A y B).

La unión de A y B es el conjunto de todos los elementos en A o B o en ambos, y se denota como:

La intersección de A y B es el conjunto de todos los elementos tanto en A como en B, y se denota como

El número de elementos en la unión de los conjuntos A y B se denota como

Y el número de elementos en la intersección de los conjuntos A y B se denota como

Todos los elementos que están en A o B, o fuera de A y B forman lo que se conoce como el universo o U.

Inclusión-Exclusión con dos conjuntos

Para contar el número de elementos en la unión de dos conjuntos (A y B), necesitamos saber el número de elementos en el conjunto A, el número de elementos en el conjunto B y el número de elementos en A y B (la intersección de A y B).

Simplemente sumando los elementos en A y B juntos contará los elementos en la intersección dos veces, por lo que necesitamos restar la intersección de A y B para obtener el número correcto de elementos en la unión de A y B. Este concepto puede ser declarado utilizando la siguiente fórmula matemática:

Otra forma de ver este concepto es utilizando un diagrama de Venn o una representación visual de conjuntos. En la Figura 1 a continuación, el círculo de la izquierda representa el conjunto A, el círculo de la derecha representa el conjunto B y la superposición representa la intersección de A y B. Todo lo contenido dentro de cualquiera de los círculos representa la unión de A y B. Dado que la región del medio está contenida en ambos círculos, se debe restar para que solo se cuente una vez. Tenga en cuenta que el universo U contiene todo dentro de la caja completa.

Figura 1: Diagrama de Venn con dos conjuntos

Ejemplos con dos conjuntos

Para dar un ejemplo más concreto, considere un grupo de personas donde 10 tienen perros, 12 tienen gatos y 5 son dueños de ambos. Queremos saber cuántas personas poseen uno o ambos. En otras palabras, queremos encontrar el número de elementos en la unión de dueños de perros y dueños de gatos. Usando D (para perros) y C (para gatos), obtenemos la siguiente fórmula:

Ahora podemos conectar los números del enunciado del problema:

El resultado son 17 personas que poseen perros, gatos o ambos.

Ahora consideremos un ejemplo que contará la cantidad de elementos que no están en un determinado conjunto. Supongamos que tenemos un grupo de 100 estudiantes. 20 están tomando matemáticas discretas (D), 30 están tomando programación Java (J) y 6 están tomando ambas clases. Queremos saber el número que no está tomando ninguna clase. En el diagrama de Venn de la Figura 1, esto representa la región que está fuera de ambos círculos. La idea es primero encontrar el número de estudiantes que toman cualquiera de las clases (el sindicato):

El resultado son 44 estudiantes que toman una clase o ambas. Ahora podemos restar 44 del número total de estudiantes en el universo (100) para obtener 56 estudiantes que no están tomando ninguna clase.

Como otro ejemplo, suponga que queremos contar el número de estudiantes que toman matemáticas discretas pero no Java. Para encontrar este número, podemos tomar el número que toma matemáticas discretas (20) y restar el número que toma ambas clases (6) para obtener 14 estudiantes que toman matemáticas discretas pero no Java.

Inclusión-Exclusión con Tres Conjuntos

Ahora que hemos tenido algo de práctica con dos conjuntos, consideremos cómo contar elementos que involucran tres conjuntos (A, B y C). Si sumamos el número de elementos en cada uno de los tres conjuntos, volveremos a contar los elementos que están en más de un conjunto varias veces, como se muestra en la Figura 2 a continuación. Las regiones donde hay dos conjuntos superpuestos se contarán dos veces y la región donde los tres conjuntos se superponen se contará tres veces.

Figura 2: Diagrama de Venn con tres conjuntos y recuentos de regiones

Si restamos cada uno de los pares de conjuntos, entonces la fórmula se ve así:

El problema con este enfoque es que la región media donde se cruzan los tres conjuntos no se contará en absoluto. Esto se muestra en la Figura 3.

Figura 3: Diagrama de Venn con tres conjuntos y recuentos de regiones ajustados

Para solucionar esto, simplemente podemos volver a agregar la intersección de los tres conjuntos, de modo que la fórmula ahora se verá así:

Cada una de las regiones del diagrama de Venn ahora se contará exactamente una vez.

Ejemplos con tres conjuntos

Trabajemos en un escenario que involucra tres conjuntos. Considere el ejemplo anterior de 100 estudiantes, donde 20 están tomando matemáticas discretas, 30 están tomando Java y 6 están tomando ambos. Ahora suponga que 25 de los 100 están tomando diseño web, 8 están tomando tanto matemáticas discretas como diseño web, 10 están tomando Java y diseño web y 5 están tomando las tres clases.

Para encontrar el número de estudiantes que toman cualquiera de las clases (una clase, dos clases o las tres clases), podemos insertar todos los números conocidos en la fórmula:

El resultado son 56 estudiantes que toman una o más de las tres clases.

Supongamos que en el ejemplo anterior, se nos dio el número de estudiantes en cualquiera de las clases (la unión) y se nos pidió que encontráramos el número de estudiantes en las tres clases (la intersección). Podemos tomar la fórmula anterior y resolver la intersección de las tres clases, dada por

Fórmula general del principio de inclusión-exclusión

El principio de inclusión-exclusión se puede extender a cualquier número de conjuntos n , donde n es un número entero positivo. El principio general de inclusión-exclusión se define de la siguiente manera:

Sean A 1 , A 2 ,…, A n conjuntos finitos. Entonces

Por ejemplo, al aplicar esta fórmula a cuatro conjuntos se obtiene:

Resumen de la lección

Esta lección cubrió el principio de inclusión-exclusión que se puede utilizar para contar el número de elementos dentro de las colecciones que tienen elementos en común. Comenzamos con conceptos fundamentales de la teoría de conjuntos , incluida la unión y la intersección , que son necesarios para resolver problemas de conteo utilizando el principio de inclusión-exclusión. Luego trabajamos en las fórmulas y ejemplos de cada uno, incluidos los de dos conjuntos y tres conjuntos. Finalmente, presentamos una fórmula general para el principio de inclusión-exclusión aplicado a n conjuntos.