Intuición del principio de inclusión-exclusión

Question

Muchos de nosotros estamos familiarizados con el principio de inclusión-exclusión . Creo que el principio tiene todo el sentido cuando se aplica a los dos o tres conjuntos y tenemos lo siguiente:

$|A\cup B|=|A|+|B|-|A\cap B|$

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A+B+C|\text{.}$

Sin embargo, no es tan fácil entender cómo funciona esto en el caso general. En lugar de una prueba rigurosa, es fácil ver que el IEP se basa en el siguiente principio: supongamos que $x$ es miembro de $n$ conjuntos. Entonces $x$ se cuenta $n$ veces en el primer recuento, restado $n$ elija $2$ veces en el segundo recuento, sumado de nuevo en $n$ elija $3$ veces en el tercer recuento, etc. . En otras palabras:

$${n \choose 1}-{n\choose 2}+{n\choose 3}-{n\choose 4}+\cdots+(-1)^{n+1}{n \choose n}=1$$

O, quizás sea más apropiado escribirlo como

$${n\choose 0}-{n \choose 1}+{n\choose 2}+\cdots+(-1)^{n}{n \choose n}=0$$

Debo aclarar que la prueba de esto es fácil de hacer algebraicamente pero estoy buscando un intuitivo explicación de la propiedad anterior, y tengo curiosidad por saber cómo ve la gente el IEP desde una perspectiva combinatoria.

Answer 1

La forma en que suelo pensar en el Principio de Inclusión-Exclusión es algo así:

Si algo está en $n$ de la $S_j$ se contará $\binom{n}{k}$ veces en la suma de los tamaños de las intersecciones de $k$ de la $S_j$ . Por lo tanto, se contará $$ \sum_{k\ge1}(-1)^{k-1}\binom{n}{k}=1\tag{1} $$ tiempo en la expresión $$ \begin{align} &\overbrace{\sum_i\left|S_i\right|}^{\binom{n}{1}}-\overbrace{\sum_{i\lt j}\left|S_i\cap S_j\right|}^{\binom{n}{2}}+\overbrace{\sum_{i\lt j\lt k}\left|S_i\cap S_j\cap S_k\right|}^{\binom{n}{3}}-\dots\tag{2} \end{align} $$ donde la expresión sobre cada suma es el número de veces que un objeto en $n$ de la $S_j$ se contará en esa suma.

Así, debido a $(1)$ cualquier objeto, no importa cuántos de los $S_j$ está en (no importa lo que $n$ es), se contará sólo una vez en $(2)$ .

Answer 2

Un aspecto esencial del Principio de Inclusión-Exclusión (PEI) es la transformación de al menos información a exactamente información.

• Si se cuentan los objetos que tienen al menos un número de propiedades es sencillo, pero contar los objetos que tienen exactamente una serie de propiedades es difícil, entonces entra en juego el PEI.

• El objetos están representados por los elementos contenidos en $A_1,\dots,A_n$ y el propiedades de un elemento $x$ son los conjuntos $A_j,1\leq j\leq n$ que contienen $x$ .

Si tenemos esto esencia de IEP en mente y nos fijamos en la expresión:

\begin {align*} \left | \bigcup_ {j=1}^{n}A_j \right |= \sum_ {j=1}^{n} \left |A_j \right | - \sum_ {1 \leq i \leq j \leq n} \left |A_i \cap A_j \right | \pm\cdots +(-1)^{n-1} \left | \bigcap_ {j=1}^{n}A_j \right | \end {align*}

observamos que el lado derecho (RHS) está formado por sumandos con al menos información.

Obsérvese que el sumando

$$\left|A_i\cap A_j\right|\quad \text{in}\quad\sum_{1\leq i \leq j \leq n}\left|A_i\cap A_j\right|$$

no es sólo el número de elementos que están en $A_i$ y $A_j$ es más precisamente el número de elementos que son al menos en $A_i$ y $A_j$ ya que los elementos $x$ en $A_i\cap A_j$ también pueden estar contenidos en otros conjuntos de $A_1,\dots,A_n$ .

Mientras que el LHS $$\left|\bigcup_{j=1}^{n}A_j\right|$$ presenta el número de elementos que exactamente en $\bigcup_{j=1}^{n}A_j$ .

Observamos que el IEP transforma la información de recuento con al menos propiedades en la información de recuento con exactamente propiedades.

Nota: Esta conexión intuitiva entre al menos y exactamente la información tiene una representación formal. Mediante las funciones generadoras se obtiene una especie de vista de pájaro a mano, que transforma la al menos a un exactamente información tan simple como cambiar por uno del argumento. Para más información sobre este enfoque, puede consultar la sección 4.2 de H.S. Wilfs Generación de funcionalidades .