7.2: La fórmula de inclusión-exclusión

Ahora que tenemos una comprensión de lo que queremos decir con una propiedad, veamos cómo podemos usar este concepto para generalizar el proceso que usamos en los dos primeros ejemplos de la sección anterior.

Dejar\(X\) ser un conjunto y dejar\(\mathcal{P}=\{P_1,P_2,…,P_m\}\) ser una familia de propiedades. Entonces para cada subconjunto\(S \subseteq [m]\), vamos a\(N(S)\) denotar el número de elementos de los\(X\) cuales satisfacen la propiedad\(P_i\) para todos\(i \in S\). Tenga en cuenta que si\(S= \emptyset\)\(N(S)=|X|\), entonces, como cada elemento de\(X\) satisface cada propiedad en\(S\) (que no contiene propiedades reales).

Volviendo por un momento al Ejemplo 7.1 con\(P_1\) ser “es un estudiante de informática” y\(P_2\) ser “es masculino”, observamos que\(N(\{1\})=47\), ya que hay 47 carreras de informática en la clase. También,\(N(\{2\})=51\) ya que 51 de los alumnos son de sexo masculino. Por último,\(N(\{1,2\})=45\) ya que en la clase hay 45 carreras masculinas de ciencias de la computación.

En los ejemplos de la sección anterior, restamos\(N(S)\) para los conjuntos\(S\) de tamaño 1 y luego agregamos de nuevo\(N(S)\) para el conjunto de propiedades de tamaño 2, ya que restamos el número de cosas con ambas propiedades (carreras masculinas de informática o soluciones con ambas\(x_3>7\) y \(x_4′>8\)) dos veces. Simbólicamente, determinamos que el número de objetos que no satisfacían ninguna de las propiedades era

\(N(\emptyset) - N(\{1\}) - N(\{2\}) + N(\{1,2\})\).

Supongamos que teníamos tres propiedades\(P_1,P_2\), y\(P_3\). ¿Cómo contaríamos el número de objetos que satisfacen ninguna de las propiedades? Como antes, comenzamos restando para cada uno de\(P_1, P_2\), y\(P_3\). Ahora hemos eliminado los objetos satisfaciendo ambos\(P_1\) y\(P_2\) dos veces, así que debemos volver a\(N(\{1,2\})\) agregar. de igual manera, debemos hacer esto para los objetos que satisfacen tanto\(P_2\)\(P_3\) y y ambos\(P_1\) y\(P_3\). Ahora pensemos en los objetos que satisfacen las tres propiedades. Se cuentan en\(N(\emptyset)\), se eliminan tres veces por los\(N(\{i\})\) términos y se suman tres veces por los\(N(\{i,j\})\) términos. Así, ¡siguen siendo contabilizados! Así, aún debemos restar\(N(\{1,2,3\})\) para obtener el número deseado:

\(N(\emptyset) - N(\{1\}) - N(\{2\}) - N(\{3\}) + N(\{1,2\}) + N(\{2,3\}) + N(\{1,3\}) - N(\{1,2,3\})\).

Podemos generalizar esto como el siguiente teorema:

Teorema 7.7. Principio de Inclusión-Exclusión.

El número de elementos de los\(X\) cuales no satisfacen ninguna de las propiedades en\(\mathcal{P}\) viene dado por

\(\displaystyle \sum_{S \subseteq [m]} (-1)^{|S|}N(S)\).

Prueba

Se procede por inducción sobre el número\(m\) de propiedades. Si\(m=1\), entonces la fórmula se reduce a\(N(\emptyset)−N(\{1\})\). Esto es correcto ya que dice solo que el número de elementos que no satisfacen la propiedad\(P_1\) es el número total de elementos menos el número que sí satisfacen la propiedad\(P_1\).

Ahora asuma validez cuando\(m \leq k\) para algunos\(k \geq 1\) y considere el caso donde\(m=k+1\). Let\(X′=\{x \in X:x\) satisface\(P_{k+1}\}\) y\(X″=X−X′\) (es decir,\(X″\) es el conjunto de elementos que no satisfacen\(P_{k+1}\)). También, vamos\(Q=\{P_1,P_2,…,P_k\}\). Entonces para cada subconjunto\(S \subseteq [k]\), vamos a\(N′(S)\) contar el número de elementos de propiedad\(X′\) satisfactoria\(P_i\) para todos\(i \in S\). Además, vamos a\(N″(S)\) contar el número de elementos de propiedad\(X″\) satisfactoria\(P_i\) para cada uno\(i \in S\). Tenga en cuenta que\(N(S)=N′(S)+N″(S)\) para cada\(S \subseteq [k]\).

Let\(X_0′\) denotar el conjunto de elementos en los\(X′\) que satisfacer ninguna de las propiedades en\(Q\) (en otras palabras, aquellos que satisfacen sólo\(P_{k+1}\) de\(\mathcal{P}\)), y dejar\(X_0″\) denotar el conjunto de elementos de los\(X″\) cuales satisfacer ninguna de las propiedades en\(Q\), y por lo tanto ninguna de las propiedades en\(\mathcal{P}\).

Ahora por la hipótesis inductiva, sabemos

\(|X_0'| = \displaystyle \sum_{S \subseteq [k]} (-1)^{|S|}N'(S)\)y\(|X_0"| = \displaystyle \sum_{S \subseteq [k]} (-1)^{|S|} N"(S)\).

De ello se deduce que

\(|X_0"| = \displaystyle \sum_{S \subseteq [k]} (-1)^{|S|}N'(S) = \displaystyle \sum_{S \subseteq [k]} (-1)^{|S|} (N(S) - N'(S))\)

\(= \displaystyle \sum_{S \subseteq [k]} (-1)^{|S|}N(S) + \sum_{S \subseteq [k]} (-1) ^{|S|+1} N(S \cup \{k+1\})\)

\(= \displaystyle \sum_{S \subseteq [k+1]} (-1)^{|S|}N(S)\).