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

Volvamos a un problema que hemos mencionado pero no resuelto:

Ejemplo \(\PageIndex{1}\)

¿Cuántos submulticonjuntos del multiconjunto\(\{2\cdot a, 4\cdot b, 3\cdot c\}\) tienen tamaño 7?

Solución

Reformulamos el problema: esta es la cantidad de soluciones a\(x_1+x_2+x_3=7\) con\(0\le x_1\le 2\),\(0\le x_2\le 4\),\(0\le x_3\le 3\). Sabemos que el número de soluciones en enteros no negativos es\({7+3-1\choose 3-1}={9\choose 2}\), por lo que este es un recuento excesivo, ya que contamos soluciones que no cumplen con las restricciones de límite superior. Por ejemplo, esto incluye algunas soluciones con\(x_1\ge 3\); ¿cuántas de estas hay? Este es un problema que podemos resolver: es el número de soluciones a\(x_1+x_2+x_3=7\) con\(3\le x_1\),\(0\le x_2\),\(0\le x_3\). Esto es lo mismo que el número de soluciones no negativas de\(y_1+y_2+y_3=7-3=4\), o\({4+3-1\choose 3-1}={6\choose 2}\). Así,\({9\choose 2}-{6\choose 2}\) corrige este exceso de conteo.

Si así mismo corrigimos para el exceso de soluciones con\(x_2\ge 5\) y\(x_3\ge 4\), obtenemos\({9\choose 2}-{6\choose 2}-{4\choose 2}-{5\choose 2}\). ¿Es esto correcto? No necesariamente, porque ahora tenemos un posible recuento insuficiente: hemos restado dos veces 1 para una solución en la que ambos\(x_1\ge 3\) y\(x_2\ge 5\), cuando deberíamos haber restado apenas 1. No obstante, por buena fortuna, no existen tales soluciones, ya que\(3+5>7\). Pero lo mismo se aplica a los otros pares de variables: ¿Cuántas soluciones tienen\(x_1\ge 3\) y\(x_3\ge 4\)? Es fácil ver que sólo hay una solución de este tipo, a saber\(3+0+4=7\). Por último, no hay soluciones con\(x_2\ge 5\) y\(x_3\ge 4\), por lo que el recuento corregido es ahora\({9\choose 2}-{6\choose 2}-{4\choose 2}-{5\choose 2}+1\). Esto no toma en cuenta ninguna solución en la que\(x_1\ge 3\),\(x_2\ge 5\), y\(x_3\ge 4\), pero no hay ninguna de estas, por lo que el recuento real es

\[{9\choose 2}-{6\choose 2}-{4\choose 2}-{5\choose 2}+1= 36-15-6-10+1=6.\nonumber\]

Esto es lo suficientemente pequeño como para que no sea difícil de verificar enumerando todas las soluciones.

Entonces resolvimos este problema, pero es evidente que podría haber sido mucho peor, si el número de variables fuera mayor y hubiera muchos sobrelatos complicados y recuentos inferiores. Notablemente, es posible agilizar este tipo de argumentos; seguirá siendo, a menudo, bastante desordenado, pero el razonamiento será más sencillo.

Empecemos por reformular el ejemplo. \(S\)Sea el conjunto de todas las soluciones no negativas para\(x_1+x_2+x_3=7\), que\(A_1\) sean todas las soluciones con\(x_1\ge 3\),\(A_2\) todas las soluciones con\(x_2\ge 5\) y\(A_3\) todas las soluciones con\(x_3\ge 4\). Queremos saber el tamaño de\(A_1^c\cap A_2^c\cap A_3^c\), las soluciones para las que no es cierto eso\(x_1\ge 3\) y no es cierto eso\(x_2\ge 5\) y no cierto eso\(x_3\ge 4\). Examinando nuestra solución, vemos que el recuento final es

\[\eqalign{ |S|-|A_1|&-|A_2|-|A_3|+|A_1\cap A_2|+|A_1\cap A_3|+|A_2\cap A_3|- |A_1\cap A_2\cap A_3|\cr &=36-15-6-10+0+1+0-0.\cr }\nonumber\]

Este patrón es completamente general:

Teorema \(\PageIndex{1}\): The Inclusion-Exclusion Formula

Si\(A_i\subseteq S\) para\(1\le i\le n\) entonces\[|A_1^c\cap\cdots\cap A_n^c|= |S|-|A_1|-\cdots-|A_n|+|A_1\cap A_2|+\cdots-|A_1\cap A_2\cap A_3|-\cdots,\nonumber\] o de manera más compacta:\[|\bigcap_{i=1}^n A_i^c|=|S|+\sum_{k=1}^n (-1)^k \sum|\bigcap_{j=1}^k A_{i_j}|,\nonumber\] donde la suma interna está sobre todos los subconjuntos\(\{i_1,i_2,\ldots,i_k\}\) de\(\{1,2,\ldots,n\}\).

Prueba

Necesitamos demostrar que cada elemento de\(\bigcap_{i=1}^n A_i^c\) se cuenta una vez por el lado derecho, y cada otro elemento de\(S\) se cuenta cero veces. El primero de estos es fácil: si\(x\in \bigcap_{i=1}^n A_i^c\) entonces por cada\(i\),\(x\notin A_i\), así\(x\) es en ninguno de los sets que involucran el\(A_i\) en el lado derecho, y así\(x\) se cuenta, una vez, por el término\(|S|\).

Ahora supongamos\(x\notin \bigcap_{i=1}^n A_i^c\). En el lado derecho,\(x\) se cuenta una vez por el término\(|S|\). Para algunos valores\(i_1,i_2,\ldots,i_k\),\(x\in A_{i_m}\),\(1\le m\le k\), y no\(x\) está en los conjuntos restantes\(A_i\). Entonces\(x\) se cuenta cero veces por cualquier término que involucre un\(A_i\) con\(i\notin \{i_1,i_2,\ldots,i_k\}\), y se cuenta una vez, positiva o negativamente, por cada término que involucra solamente\(A_{i_1},A_{i_2},\ldots,A_{i_k}\). Hay\(k\) términos de la forma\(-|A_{i_m}|\), que cuentan\(x\) un total de\(-k\) veces. Hay\(k\choose 2\) términos de la forma\(|A_{i_l}\cap A_{i_m}|\), contando\(x\) un total de\(k\choose 2\) veces. Continuando de esta manera, vemos que el conteo final para\(x\) en el lado derecho es

\[1-k+{k\choose 2}-{k\choose 3}+\cdots+(-1)^k{k\choose k},\nonumber\]

o de forma más compacta

\[\sum_{i=0}^k (-1)^i{k\choose i}.\nonumber\]Sabemos que esta suma alterna de coeficientes binomiales es cero, por lo que\(x\) se cuenta cero veces, según se desee. (Ver ecuación 1.4.1.)

Una forma alternativa de la fórmula de exclusión de inclusión es a veces útil.

Corolario \(\PageIndex{1}\)

Si\(A_i\subseteq S\) para\(1\le i\le n\) entonces\[|\bigcup_{i=1}^n A_i|=\sum_{k=1}^n (-1)^{k+1} \sum|\bigcap_{j=1}^k A_{i_j}|,\nonumber\] donde la suma interna es sobre todos los subconjuntos\(\{i_1,i_2,\ldots,i_k\}\) de\(\{1,2,\ldots,n\}\).

Prueba

Dado que\((\bigcup_{i=1}^n A_i)^c=\bigcap_{i=1}^n A_i^c\),

\[\eqalign{ |\bigcup_{i=1}^n A_i|&=|S|-|\bigcap_{i=1}^n A_i^c|\cr &=|S|-(|S|+\sum_{k=1}^n (-1)^k \sum|\bigcap_{j=1}^k A_{i_j}|)\cr &=(-1)\sum_{k=1}^n (-1)^k \sum|\bigcap_{j=1}^k A_{i_j}|\cr &=\sum_{k=1}^n (-1)^{k+1}\sum|\bigcap_{j=1}^k A_{i_j}|. }\nonumber\]

Dado que el lado derecho de la fórmula de inclusión-exclusión consiste en\(2^n\) términos a agregar, todavía puede ser bastante tedioso. En algunos casos agradables, todas las intersecciones del mismo número de conjuntos tienen el mismo tamaño. Dado que existen\(n\choose k\) posibles intersecciones que consisten en\(k\) conjuntos, la fórmula se convierte en\[\label{eq:1}\eqalignno{ |\bigcap_{i=1}^n A_i^c|&=|S|+\sum_{k=1}^n (-1)^k{n\choose k}m_k,\cr }\] donde\(m_k\) está el tamaño de una intersección\(k\) de los conjuntos.

Ejemplo\(\PageIndex{2}\)

Encuentre el número de soluciones para\(x_1+x_2+x_3+x_4=25\),\(0\le x_i\le 10\). \(A_i\)Dejen ser las soluciones de\(x_1+x_2+x_3+x_4=25\) con\(x_i\ge 11\). El número de soluciones con\(x_i\ge 0\) para todos\(i\) es\({25+4-1\choose 4-1}={25+3\choose 3}\). También\(|A_i|={14+3\choose 3}\), y\(|A_i\cap A_j|={3+3\choose 3}\). No hay soluciones con 3 o 4 de las variables mayores a 10. De ahí que el número de soluciones sea

\[{25+3\choose 3}-{4\choose 1}{14+3\choose 3}+{4\choose 2}{3+3\choose 3}=676.\nonumber\]

Colaboradores y Atribuciones

• Template:ContribGuichard