El principio de inclusión y exclusión permite contar elementos que pertenecen a uno o varios conjuntos sin duplicar los que aparecen en sus zonas de solapamiento. Es una herramienta esencial para consultas, filtros, probabilidades y problemas de conteo.
Contar elementos de varios grupos parece tan simple como sumar sus cantidades. El problema aparece cuando un mismo elemento puede pertenecer a más de un grupo: al sumar, ese elemento se cuenta varias veces.
El principio de inclusión y exclusión corrige ese exceso. Primero incluimos los tamaños de los conjuntos, luego excluimos las intersecciones contadas dos veces y, si hay tres conjuntos, volvemos a incluir la intersección triple.
La unión A ∪ B contiene los elementos que están en A, en B o en ambos. La intersección A ∩ B contiene solamente los elementos que pertenecen simultáneamente a A y a B.
La cantidad de elementos de un conjunto finito S se denota |S|. En el ejemplo, |A| = 4, |B| = 3, |A ∩ B| = 2 y |A ∪ B| = 5.
Si sumamos |A| + |B| en el ejemplo anterior obtenemos 4 + 3 = 7. Sin embargo, la unión tiene solo 5 elementos porque 3 y 4 se contaron una vez en A y otra vez en B.
La intersección cuantifica exactamente el exceso. Restarla una vez deja a cada elemento de la unión contado exactamente una vez.
Para dos conjuntos finitos A y B, la fórmula es:
La regla funciona tanto si los conjuntos son disjuntos como si se superponen. Si no comparten elementos, |A ∩ B| = 0 y la fórmula se reduce a una suma ordinaria.
Separaremos los elementos de A ∪ B en tres clases disjuntas: los que están solo en A, los que están solo en B y los que están en ambos.
Esta explicación también muestra por qué no debemos restar una intersección dos veces: los elementos compartidos pasarían a no contarse.
En una colección de documentos, 45 contienen la palabra «algoritmo», 32 contienen «grafo» y 12 contienen ambas. ¿Cuántos contienen al menos una de las dos palabras?
La consulta OR corresponde a la unión. Si una aplicación suma los resultados de dos filtros sin eliminar coincidencias, mostrará duplicados y dará un total incorrecto.
El tipo Set guarda valores sin repetidos y resulta apropiado para representar conjuntos finitos.
function union(a, b) {
return new Set([...a, ...b]);
}
function interseccion(a, b) {
return new Set([...a].filter(valor => b.has(valor)));
}
const a = new Set([1, 2, 3, 4]);
const b = new Set([3, 4, 5]);
console.log([...union(a, b)]); // [1, 2, 3, 4, 5]
console.log([...interseccion(a, b)]); // [3, 4]La cardinalidad de un Set se obtiene con .size. El orden mostrado al convertirlo en arreglo depende del orden de inserción y no forma parte de la definición matemática de conjunto.
function contarUnionDosConjuntos(a, b) {
const ambos = interseccion(a, b);
return a.size + b.size - ambos.size;
}
const usuariosA = new Set(["ana", "bea", "carlos", "diego"]);
const usuariosB = new Set(["carlos", "diego", "elena"]);
console.log(contarUnionDosConjuntos(usuariosA, usuariosB)); // 5
console.log(union(usuariosA, usuariosB).size); // 5Comparar la fórmula con la unión construida directamente es una buena manera de probar una implementación. En conjuntos grandes, elegir entre materializar la unión o trabajar solo con cardinalidades depende de los datos disponibles.
Para tres conjuntos A, B y C se suman los tamaños individuales, se restan las intersecciones de pares y se vuelve a sumar la intersección triple:
La intersección triple se suma al final porque sus elementos fueron incluidos tres veces y excluidos tres veces; en ese punto todavía tienen conteo cero y deben aparecer una vez.
En una escuela, 60 estudiantes estudian inglés, 45 estudian francés y 40 estudian programación. Las intersecciones son: 20 estudian inglés y francés, 15 inglés y programación, 10 francés y programación, y 5 estudian las tres áreas.
El valor 105 cuenta a cada estudiante que participa en al menos una de las actividades una sola vez. Las intersecciones de pares incluyen a quienes cursan las tres, por eso la intersección triple debe compensarse.
Un elemento que pertenece a distinta cantidad de conjuntos recibe los siguientes conteos a lo largo de la fórmula:
| Ubicación del elemento | Al sumar individuales | Al restar pares | Al sumar triple | Total |
|---|---|---|---|---|
| Solo en un conjunto | 1 | 0 | 0 | 1 |
| En exactamente dos conjuntos | 2 | -1 | 0 | 1 |
| En los tres conjuntos | 3 | -3 | +1 | 1 |
La tabla es una forma útil de recordar los signos. El objetivo final de la alternancia es que cualquier elemento presente en la unión tenga coeficiente total 1.
Si tenemos los elementos explícitos, la forma más simple de contar una unión es insertarlos todos en un único Set. El propio tipo de datos elimina los duplicados.
function unionDeMuchos(conjuntos) {
const resultado = new Set();
for (const conjunto of conjuntos) {
for (const valor of conjunto) resultado.add(valor);
}
return resultado;
}
const a = new Set([1, 2, 3]);
const b = new Set([3, 4]);
const c = new Set([2, 4, 5]);
console.log(unionDeMuchos([a, b, c]).size); // 5El principio de inclusión y exclusión es especialmente útil cuando no tenemos los elementos individuales, sino solo los tamaños de las intersecciones.
¿Cuántos enteros entre 1 y 100 son divisibles por 2 o por 3? Definimos A como los múltiplos de 2 y B como los múltiplos de 3.
Los múltiplos de 6 pertenecen a ambos conjuntos; son los que se habían contado dos veces. El máximo común múltiplo conecta este problema con el algoritmo de Euclides.
function multiplosDe2O3(limite) {
const resultado = [];
for (let n = 1; n <= limite; n++) {
if (n % 2 === 0 || n % 3 === 0) resultado.push(n);
}
return resultado;
}
const valores = multiplosDe2O3(100);
console.log(valores.length); // 67La condición OR expresa la unión. Usar dos bucles separados y concatenar resultados requeriría eliminar los múltiplos de 6 repetidos; inclusión y exclusión explica de antemano cuántas repeticiones habría.
Si U es un universo finito y queremos contar los elementos que no están en A ∪ B, usamos el complemento:
La notación U \ S representa los elementos de U que no pertenecen a S. Contar el complemento suele ser más simple que contar directamente una condición negativa.
Si todos los elementos de un universo finito son igualmente probables, al dividir la fórmula por |U| obtenemos la regla de probabilidad para dos eventos:
La fórmula no requiere que A y B sean independientes. La independencia es una condición distinta que afecta cómo se calcula P(A ∩ B), no la validez de inclusión y exclusión.
Una consulta que combina filtros con OR debe devolver una fila una sola vez, aunque cumpla varias condiciones. En términos de conjuntos, el resultado es la unión de los conjuntos de filas que satisface cada filtro.
Los motores de bases de datos se ocupan normalmente de la semántica de la consulta, pero conocer la estructura de conjuntos ayuda a razonar sobre totales, índices, deduplicación y rendimiento.
Para n conjuntos finitos, se suman los tamaños de las intersecciones de un conjunto, se restan las de dos conjuntos, se suman las de tres y así sucesivamente, alternando signos.
La fórmula puede tener muchas intersecciones: para n conjuntos hay 2n - 1 términos no vacíos. Por eso es muy útil en teoría, pero puede ser costosa si n es grande y se intenta calcular de manera directa.
La técnica aparece al contar cadenas que evitan patrones, números que cumplen restricciones, asignaciones sin conflictos y soluciones que satisfacen al menos una condición. También sirve para estimar resultados de filtros que se solapan.
En programación práctica, si se dispone de todos los elementos suele ser más sencillo usar un Set. La fórmula cobra valor cuando los conjuntos son demasiado grandes, están definidos implícitamente o solo se conocen sus cardinalidades e intersecciones.
Un diagrama de Venn puede ayudar con dos o tres conjuntos. Para más conjuntos, las fórmulas y una tabla de signos suelen ser más claras que intentar dibujar todas las regiones.
Set es útil para materializar una unión concreta sin duplicados.El principio de inclusión y exclusión convierte solapamientos complejos en una suma controlada de intersecciones. En el próximo tema estudiaremos relaciones de equivalencia y de orden, que permiten describir cómo se vinculan formalmente los elementos de un conjunto.