Posgrado
  1. Introducción al análisis real  1.1. Teoría de conjuntos y lógica en el análisis real  1.1.1. Conjuntos y operaciones en teoría de conjuntos y lógica en análisis real  1.1.2. Relaciones y funciones  1.1.3. Lógica y cuantificadores  1.1.4. Cardinalidad de conjuntos  1.2. Espacio métrico  1.2.1. Introducción a conjuntos abiertos y cerrados en espacios métricos  1.2.2. Convergencia de secuencias en un espacio métrico  1.2.3. Función continua en un espacio métrico  1.2.4. Compacidad y completitud en espacios métricos en análisis real  1.3. Secuencias y series  1.3.1. Convergencia de secuencias  1.3.2. Series infinitas  1.3.3. Convergencia uniforme  1.3.4. Serie de potencias  1.4. Discriminación  1.4.1. Teorema del valor medio  1.4.2. Serie de Taylor  1.4.3. Funciones de varias variables  1.4.4. Derivada parcial  1.5. Integración  1.5.1. Integración de Riemann y Lebesgue  1.5.2. Integrales impropias  1.5.3. Teoría de la medida: una herramienta fundamental en la integración  1.5.4. Teorema de Fubini  1.6. Análisis funcional  1.6.1. Comprendiendo los espacios de Banach  1.6.2. Espacios de Hilbert  1.6.3. Operadores en espacios  1.6.4. Teoría espectral
  2. Álgebra abstracta  2.1. Entendiendo los grupos en el álgebra abstracta  2.1.1. Definiciones y ejemplos de grupos en álgebra abstracta  2.1.2. Homomorfismos de grupos  2.1.3. Introducción a los subgrupos normales  2.1.4. Teorema de Sylow  2.2. Anillos y campos  2.2.1. Ideales y anillos cociente  2.2.2. Extensiones de campos  2.2.3. Teoría de Galois  2.2.4. Anillos de polinomios  2.3. Introducción a los módulos en álgebra abstracta  2.3.1. Homomorfismo de módulos  2.3.2. Módulos libres  2.3.3. Introducción a los productos tensoriales  2.3.4. Secuencia exacta en módulos  2.4. Álgebra lineal  2.4.1. Espacio vectorial  2.4.2. Autovalores y autovectores  2.4.3. Espacio de producto interior  2.4.4. Diagonalización
  3. Topología  3.1. Topología general  3.1.1. Conjuntos abiertos y cerrados  3.1.2. Compacidad y conexión  3.1.3. Mapas continuos  3.1.4. Axioma de separación  3.2. Topología algebraica  3.2.1. Comprensión de los grupos fundamentales en la topología algebraica  3.2.2. Homotopía y homología  3.2.3. Complejo simplicial  3.2.4. Secuencias exactas en homología  3.3. Topología diferencial  3.3.1. Comprendiendo las variedades en topología diferencial  3.3.2. Funcionamiento suave  3.3.3. Espacio tangente y cotangente  3.3.4. Fibrados vectoriales
  4. Ecuaciones diferenciales  4.1. Ecuación diferencial ordinaria  4.1.1. Ecuaciones de primer orden  4.1.2. Ecuaciones lineales de segundo orden  4.1.3. Sistemas de ecuaciones diferenciales  4.1.4. Análisis de estabilidad en ecuaciones diferenciales ordinarias  4.2. Ecuaciones en derivadas parciales  4.2.1. Clasificación de EDP  4.2.2. Entendiendo las series de Fourier en ecuaciones diferenciales parciales  4.2.3. Introducción a las funciones de Green  4.2.4. Método de caracterización  4.3. Sistemas dinámicos en ecuaciones diferenciales  4.3.1. Teoría de la sostenibilidad  4.3.2. Ciclos límite en sistemas dinámicos  4.3.3. Teoría del caos  4.3.4. Teoría de bifurcación
  5. Probabilidad y estadística  5.1. Teoría de la probabilidad  5.1.1. Variables aleatorias  5.1.2. Distribuciones de probabilidad  5.1.3. Ley de los grandes números  5.1.4. Teorema del límite central  5.2. Inferencia estadística  5.2.1. Pruebas de hipótesis  5.2.2. Intervalo de confianza  5.2.3. Métodos bayesianos  5.2.4. Estimación de máxima verosimilitud  5.3. Procesos estocásticos  5.3.1. Cadenas de Markov  5.3.2. Movimiento browniano  5.3.3. Comprendiendo los procesos de Poisson  5.3.4. Martingalas: Un estudio integral en probabilidad y estadística
  6. Análisis numérico  6.1. Soluciones numéricas de ecuaciones  6.1.1. Descubrimiento original  6.1.2. Métodos iterativos  6.1.3. Análisis de convergencia  6.1.4. Cotas de error en soluciones numéricas de ecuaciones  6.2. Álgebra lineal numérica  6.2.1. Factorización de matrices  6.2.2. Cálculo de valores propios  6.2.3. Matrices dispersas  6.2.4. Técnicas de preacondicionamiento  6.3. Integración y diferenciación numérica  6.3.1. Métodos de cuadratura  6.3.2. Introducción a las diferencias finitas  6.3.3. Análisis de errores en la integración y diferenciación numérica  6.3.4. Métodos adaptativos en integración y diferenciación numérica
  7. Análisis complejo  7.1. Números complejos  7.1.1. Forma polar  7.1.2. Conjugados complejos  7.1.3. Forma exponencial de los números complejos  7.1.4. Raíces de la unidad  7.2. Funciones analíticas  7.2.1. Ecuaciones de Cauchy–Riemann  7.2.2. Series de potencias  7.2.3. Mapeo conforme  7.2.4. Funciones armónicas  7.3. Integración en el plano complejo  7.3.1. Teorema de Cauchy  7.3.2. Teorema del residuo  7.3.3. Integración de contornos  7.3.4. Transformaciones integrales
  8. Lógica matemática y fundamentos  8.1. Lógica proposicional  8.1.1. Tablas de verdad  8.1.2. Equivalencia lógica en la lógica proposicional  8.1.3. Técnicas de demostración en lógica proposicional  8.1.4. Solución en lógica proposicional  8.2. Lógica de predicados  8.2.1. Cuantificadores en lógica de predicados  8.2.2. Sistemas formales en lógica de predicados  8.2.3. Integridad y solidez  8.2.4. Teoría de modelos  8.3. Teoría de conjuntos  8.3.1. Cardinalidad y ordinalidad  8.3.2. Sistemas axiomáticos  8.3.3. Comprender la teoría de conjuntos de Zermelo-Fraenkel  8.3.4. Fuerzas en la teoría de conjuntos
  9. Personalización  9.1. Programación lineal  9.1.1. Método simplex  9.1.2. Dualidad en la programación lineal  9.1.3. Análisis de sensibilidad en programación lineal  9.1.4. Métodos de punto interior  9.2. Programación no lineal  9.2.1. Descenso de gradiente  9.2.2. Multiplicadores de Lagrange  9.2.3. Optimización convexa  9.2.4. Programación cuadrática  9.3. Optimización Combinatoria  9.3.1. Algoritmos de grafos  9.3.2. Programación entera  9.3.3. Flujo de red  9.3.4. Algoritmos de aproximación
  10. Matemáticas discretas  10.1. Teoría de grafos  10.1.1. Representación de grafos  10.1.2. Llanura y color  10.1.3. Algoritmo de camino más corto  10.1.4. Flujo de red  10.2. Compañerismo  10.2.1. Permutación y combinación  10.2.2. Función generadora  10.2.3. Relación de recurrencia  10.2.4. Comprendiendo el Principio de Inclusión-Exclusión  10.3. Criptografía  10.3.1. Aplicaciones de la teoría de números en criptografía  10.3.2. Criptografía Simétrica y Asimétrica  10.3.3. RSA y criptografía de curvas elípticas  10.3.4. Criptografía post-cuántica

Posgrado → Matemáticas discretas → Compañerismo ↓


Comprendiendo el Principio de Inclusión-Exclusión


El principio de inclusión-exclusión es un concepto esencial en la combinatoria, una rama de las matemáticas discretas que se ocupa de contar y enumerar los posibles resultados. Este principio nos ayuda a determinar el tamaño de la unión de múltiples conjuntos cuando se conocen los tamaños de los conjuntos individuales y sus intersecciones. Este principio no solo es poderoso, sino que es ampliamente aplicable en diversos campos que van desde la probabilidad y la estadística hasta la informática y la lógica.

Idea original

Comencemos con el caso más simple: dos conjuntos, A y B. El teorema afirma que para encontrar el número de elementos en la unión de dos conjuntos, A y B (denotado como |A ∪ B|), debemos comenzar sumando el número de elementos de cada conjunto por separado. Sin embargo, cuando hacemos esto, contamos los elementos que son comunes a ambos conjuntos, A ∩ B. Por lo tanto, debemos restar el número de elementos en la intersección de los dos conjuntos para corregir este doble conteo.

En la teoría de conjuntos, la fórmula para la combinación de dos conjuntos se describe de la siguiente manera:

|A ∪ B| = |A| + |B| - |A ∩ B|

Visualizar el concepto

Considere un ejemplo donde tenemos dos círculos o grupos superpuestos:

A B

En esta ilustración, el círculo azul representa el conjunto A, el círculo verde representa el conjunto B, y la región donde se superponen es la intersección A ∩ B.

Ampliación a tres conjuntos

Cuando se trata de tres conjuntos, como A, B y C, la teoría se vuelve un poco más complicada. Para la unión de tres conjuntos, el principio de inclusión-exclusión nos dice lo siguiente:

|A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

Aquí, primero sumamos los tamaños de los conjuntos individuales. Luego restamos los tamaños de todas las intersecciones por pares para corregir el conteo doble. Sin embargo, esta resta también descarta elementos que son los mismos tres veces (para cada resta por pares) en los tres conjuntos, por lo que agregamos de nuevo el tamaño de la intersección triple una vez.

Ejemplo paso a paso con tres conjuntos

Consideremos un ejemplo práctico:

  • El conjunto A representa personas a las que les gustan las manzanas.
  • El conjunto B representa personas a las que les gustan los plátanos.
  • El conjunto C representa personas a las que les gustan las cerezas.

Supongamos que tenemos los siguientes datos:

  • |A| = 30 (personas a las que les gustan las manzanas)
  • |B| = 25 (personas a las que les gustan los plátanos)
  • |C| = 20 (personas a las que les gustan las cerezas)
  • |A ∩ B| = 10 (tanto manzanas como plátanos)
  • |A ∩ C| = 5 (tanto manzanas como cerezas)
  • |B ∩ C| = 8 (tanto plátanos como cerezas)
  • |A ∩ B ∩ C| = 3 (todos tres tipos de frutas)

Aplicando el Principio de Inclusión-Exclusión:

|A ∪ B ∪ C| = 30 + 25 + 20 – 10 – 5 – 8 + 3
            = 60

Así, 60 personas gustan de al menos uno de los tres tipos de frutas.

Generalización a n conjuntos

El principio de inclusión-exclusión puede generalizarse a más de tres conjuntos. Supongamos que tenemos n conjuntos, A1, A2, ..., An. El principio se generaliza de la siguiente manera:

|A1 ∪ A2 ∪ ... ∪ An|,
∑ |Ai| - ∑ |Ai ∩ Aj| + ∑ |Ai ∩ Aj ∩ Ak| - ... + (-1)n+1 |A1 ∩ A2 ... ∩ An|

Aquí, las sumas se realizan en función del número creciente de intersecciones, y el signo cambia entre resta y suma dependiendo del número de conjuntos en cada intersección.

Ejemplo visual para tres conjuntos

A continuación, una ilustración más detallada de los tres conjuntos superpuestos:

A B C

Los tres círculos representan conjuntos. Las tres intersecciones por pares y la intersección central representan las regiones restadas y agregadas nuevamente según la fórmula de inclusión-exclusión.

Aplicaciones y ejemplos avanzados

El principio de inclusión-exclusión es increíblemente versátil y puede aplicarse en muchos escenarios, como:

1. Contar sistemas restringidos

Supongamos que se nos pide contar el número de permutaciones de los números {1, 2, ..., n} de manera que ninguno de los números aparezca en su posición original (una perturbación). El principio de inclusión-exclusión nos permite incluir y excluir sistemáticamente aquellos cálculos donde un cierto número de elementos están en sus posiciones originales.

2. Estimación de la probabilidad

En probabilidad, el principio puede usarse para calcular la probabilidad de la unión de múltiples eventos. Si conocemos la probabilidad de eventos individuales y su intersección, podemos usar el principio de inclusión-exclusión para encontrar la probabilidad de que ocurra al menos uno de los eventos.

3. Fiabilidad de red

En el diseño de redes, este principio puede evaluar la fiabilidad de sistemas complejos calculando la probabilidad de que falle al menos un componente crítico.

Trabajando en un ejemplo más complejo

Veamos un ejemplo más complejo de cuatro conjuntos:

Considere cuatro grupos de estudiantes:

  • Conjunto A: Estudiantes que juegan fútbol
  • Conjunto B: Estudiantes que juegan baloncesto
  • Conjunto C: Estudiantes que juegan criquet
  • Conjunto D: Estudiantes que juegan tenis

Suponga que tenemos los siguientes datos:

  • |A| = 40
  • |B| = 35
  • |C| = 25
  • |D| = 20
  • |A ∩ B| = 15
  • |A ∩ C| = 10
  • |A ∩ D| = 5
  • |B ∩ C| = 10
  • |B ∩ D| = 8
  • |C ∩ D| = 6
  • |A ∩ B ∩ C| = 4
  • |A ∩ B ∩ D| = 2
  • |A ∩ C ∩ D| = 1
  • |B ∩ C ∩ D| = 3
  • |A ∩ B ∩ C ∩ D| = 1

Utilizando el Principio de Inclusión-Exclusión:

|A ∪ B ∪ C ∪ D| = |A| + |B| + |C| + |D|
                    - (|A ∩ B| + |A ∩ C| + |A ∩ D| + |B ∩ C| + |B ∩ D| + |C ∩ D|)
                    + (|A ∩ B ∩ C| + |A ∩ B ∩ D| + |A ∩ C ∩ D| + |B ∩ C ∩ D|)
                    − |A ∩ B ∩ C ∩ D|
                 = 40 + 35 + 25 + 20
                   - (15 + 10 + 5 + 10 + 8 + 6)
                   + (4 + 2 + 1 + 3)
                   - 1
                 = 120 – 54 + 10 – 1
                 = 75

Por lo tanto, 75 estudiantes practican al menos uno de los cuatro deportes.

Consideraciones especiales y consejos

  • Cuando use este principio, asegúrese de calcular correctamente las intersecciones. Ignorarlas o calcularlas mal puede llevar a resultados incorrectos.
  • Este método implica sumas y restas alternas, por lo que es importante seguir los signos para garantizar la precisión.
  • La complejidad aumenta con más conjuntos, por lo que es importante una organización cuidadosa de los datos para evitar errores.

Conclusión

El principio de inclusión-exclusión es una herramienta importante en la combinatoria que permite cálculos precisos y computaciones de probabilidad en escenarios complejos. A través de la aplicación cuidadosa y la consideración de conjuntos superpuestos, el principio hace que abordar muchos problemas en las matemáticas y campos relacionados sea más manejable. Al practicar con ejemplos diversos y cada vez más complejos, uno puede entender mejor la mecánica del principio y su amplia gama de aplicaciones.


Posgrado → 10.2.4


U
username
0%
completado en Posgrado

← Anterior (10.2.3)
Relación de recurrencia
Siguiente (10.3) →
Criptografía

Comentarios 



Comprendiendo el Principio de Inclusión-Exclusión

https://www.buddymath.com/g/10.2.4?bmal=es