Conjuntos y relaciones · Definición

Principio de inclusión-exclusión

matemáticas discretasconteoconjuntos

Antes de empezar necesitas conocer

Resuelve el problema de contar «los que cumplen al menos una propiedad» cuando las propiedades se traslapan.

Definición

Cuenta los elementos de la unión de conjuntos finitos \(A\), \(B\), \(C\), … sumando sus tamaños y corrigiendo lo contado de más en las intersecciones.

\[\begin{aligned}|A\cup B|&=|A|+|B|-|A\cap B|\\|A\cup B\cup C|&=|A|+|B|+|C|\\&\quad-|A\cap B|-|A\cap C|-|B\cap C|\\&\quad+|A\cap B\cap C|\end{aligned}\]

Si se suman \(|A|\) y \(|B|\), los elementos de \(A\cap B\) se cuentan dos veces; por eso se resta \(|A\cap B|\) una vez. Con tres conjuntos, restar las tres intersecciones dobles quita de más a los elementos que están en los tres (los contó tres veces y los restó tres veces), de modo que hay que sumar \(|A\cap B\cap C|\).

En general, para \(n\) conjuntos los términos alternan de signo: se suman los tamaños individuales, se restan las intersecciones de dos, se suman las de tres, y así sucesivamente. Cada elemento de la unión termina contado exactamente una vez, lo que puede verificarse con el binomio de Newton.

Un ejemplo guía: los enteros de 1 a 100 divisibles entre 2 o 3 son \(50+33-16=67\), porque los 16 múltiplos de 6 se contaron dos veces. Restando de 100 se obtienen los que no son divisibles por ninguno: 33. Este truco de contar el complemento es muy común.

Los errores típicos son olvidar el término de la intersección triple o aplicar el principio a conjuntos que no son finitos. Si los conjuntos son disjuntos, todas las intersecciones son vacías y se recupera la regla de la suma.

Para pensar

¿Por qué con tres conjuntos se suma al final \(|A\cap B\cap C|\)?

Un elemento en los tres conjuntos se suma tres veces y se resta tres veces en las intersecciones dobles; queda contado cero veces y hay que reponerlo una vez.

¿Cuánto vale \(|A\cup B|\) si \(A\) y \(B\) son disjuntos?

Vale \(|A|+|B|\), pues \(|A\cap B|=0\); es la regla de la suma.

Ejercicios 10

  1. Si \(|A|=12\), \(|B|=9\) y \(|A\cap B|=4\), ¿cuánto vale \(|A\cup B|\)?
  2. De 30 estudiantes, 18 juegan fútbol, 15 juegan básquetbol y 7 juegan ambos. ¿Cuántos no juegan ninguno?
  3. ¿Cuántos enteros de 1 a 100 son divisibles entre 2 o entre 3?
  4. ¿Cuántos enteros de 1 a 100 son divisibles entre 2, 3 o 5?
  5. ¿Cuántos enteros de 1 a 100 no son divisibles entre 2 ni entre 3?
  6. Se sabe que \(|A|=10\), \(|B|=8\), \(|C|=6\), \(|A\cap B|=3\), \(|A\cap C|=2\), \(|B\cap C|=1\) y \(|A\cap B\cap C|=1\). ¿Cuánto vale \(|A\cup B\cup C|\)?
  7. Si \(|A\cup B|=|A|+|B|\), ¿qué se concluye?
  8. ¿Cuántas cadenas binarias de longitud 8 empiezan con 1 o terminan con 00?
  9. Si \(|A\cup B|=20\), \(|A|=14\) y \(|B|=11\), ¿cuánto vale \(|A\cap B|\)?
  10. ¿Cuántos enteros de 1 a 1000 no son divisibles entre 3, 5 ni 7?

Después de esto

Referencias

  • Kenneth H. Rosen, Discrete Mathematics and Its Applications, 8th edition, McGraw-Hill, 2019. §8.5
  • Susanna S. Epp, Discrete Mathematics with Applications, 5th edition, Cengage, 2019. §9.3
  • Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, 5th edition, Pearson, 2003. §8.1