Principio de inclusión-exclusión generalizado

Question

En las respuestas a las preguntas combinatorias, a veces utilizo el hecho de que si hay $a_k$ formas de elegir $k$ de $n$ condiciones y cumplirlas, entonces hay

$$ \sum_{k=j}^n(-1)^{k-j}\binom kja_k $$

maneras de cumplir exactamente $j$ de las condiciones. Esto es cierto porque un caso en el que exactamente $m$ se cumplan las condiciones se cuenta $\binom mk$ veces en $a_k$ y por lo tanto contribuye

$$ \sum_{k=j}^n(-1)^{k-j}\binom kj\binom mk=\delta_{jm}\;. $$

En particular, si el número de formas de cumplir $k$ condiciones particulares es la misma, $b_k$ para todas las opciones del $k$ condiciones, entonces $a_k=\binom nkb_k$ y hay

$$ \sum_{k=j}^n(-1)^{k-j}\binom kj\binom nkb_k $$

maneras de cumplir exactamente $j$ de las condiciones.

He descubierto que la inclusión-exclusión parece aplicarse casi exclusivamente al caso $j=0$ , para encontrar el número de formas de cumplir ninguna (o, complementariamente, al menos una) de las condiciones, y que muchos, incluso usuarios muy experimentados, no están familiarizados con esta generalización. Eso me ha llevado a buscar una referencia al respecto, pero no he podido encontrarla. Así que mis preguntas son:

¿Es conocido este principio más general de inclusión-exclusión?
Si es así, ¿podría proporcionar una referencia para que yo pueda señalar cuando me pregunten al respecto?

Answer 1

Este es el Corolario 5.2 de la página 184 del excelente libro de Martin Aigner Curso de Enumeración .

Answer 2

Las respuestas a Probabilidad de elegir los sobres me hizo darme cuenta de que en realidad hay una prueba combinatoria directa de este principio.

Denota por $C$ el conjunto de condiciones y por $c_{S\ell}$ el número de formas de cumplir las condiciones en $S\subseteq C$ y exactamente $\ell$ más. Por inclusión-exclusión estándar, el número de formas de cumplir exactamente las condiciones en $S$ es

$$ \sum_{\ell=0}^{|C|-|S|}(-1)^\ell c_{S\ell}\;. $$

Por lo tanto, el número de formas de cumplir exactamente $j$ condiciones es

\begin{eqnarray} \sum_{S\subseteq C\atop|S|=j}\sum_{\ell=0}^{|C|-|S|}(-1)^\ell c_{S\ell} &=& \sum_{\ell=0}^{n-j}\sum_{S\subseteq C\atop|S|=j}(-1)^\ell c_{S\ell} \\ &=& \sum_{\ell=0}^{n-j}(-1)^\ell\binom{j+\ell}ja_k \\ &=& \sum_{k=j}^n(-1)^{k-j}\binom kja_k \;, \end{eqnarray}

ya que cada conjunto $S$ con $|S|=j$ aparece $\binom{j+\ell}j$ tiempos.

Esto también sugiere otra forma del resultado especializado para el caso en que el número de formas de cumplir $k$ condiciones es la misma, $b_k$ para todas las opciones del $k$ condiciones. En ese caso tenemos $c_{S\ell}=\binom{n-j}\ell b_{j+\ell}$ independiente de $S$ y la primera suma anterior es la misma para todos los $\binom nj$ opciones de $j$ condiciones, por lo que el recuento es

$$ \binom nj\sum_{\ell=0}^{n-j}(-1)^\ell \binom{n-j}\ell b_{j+\ell} =\binom nj\sum_{k=j}^n(-1)^{k-j}\binom{n-j}{k-j}b_k\;, $$

y como

$$ \binom nj\binom{n-j}{k-j}=\binom kj\binom nk\;, $$

esto coincide con

$$ \sum_{k=j}^n(-1)^{k-j}\binom kj\binom nkb_k\;, $$

pero con la ventaja de que uno de los coeficientes del binomio es constante y puede quedar fuera de la suma.

Answer 3

Otra referencia es la sección IV.3, "La realización de m entre N eventos", en Introducción a la teoría de la probabilidad y sus aplicaciones, volumen I, tercera edición por William Feller, p. 106.

Answer 4

"A veces utilizo el hecho de que si hay $a_{k}$ formas de elegir $k$ de $n$ condiciones y cumplirlas..."

En esta respuesta opto por una configuración que comienza con un conjunto $X$ que contiene lo que que usted llama maneras como elementos. Cada uno de los $n$ condiciones se corresponde con un subconjunto de $X$ que contiene exactamente las formas de cumplir la condición.

Así que permítanme introducir un conjunto de índices $I$ con cardinalidad $n$ y la colección $\left\{ A_{i}\mid i\in I\right\} $ donde $A_{i}\subseteq X$ contiene las formas que cumplen la condición $i$ .

Para $J\subseteq I$ definimos: $$A_{J}:=\bigcap_{i\in J}A_{i}$$ en la convención que $A_{\varnothing}=X$ .

Entonces $a_{k}$ mencionados anteriormente pueden ser reconocidos como: $$a_k=\sum_{J\subseteq I\wedge\left|J\right|=k}\left|A_{J}\right|$$

En el caso especial de que la cardinalidad de $J$ es determinante para la cardinalidad de $A_{J}$ y $b_{k}:=\left|A_{J}\right|$ siempre que $\left|J\right|=k$ tenemos la igualdad: $$a_{k}=\binom{n}{k}b_{k}$$ que también se menciona en su pregunta.

Por último, para los enteros no negativos $j$ definimos: $$U_{j}:=\left\{ x\in X\mid\sum_{i\in J}\mathbf{1}_{A_{i}}\left(x\right)=j\right\}\text{ and }u_j:=|U_j| $$

Para que tengamos $x\in U_{j}$ si $x$ es una forma que cumple exactamente $k$ de las condiciones, y -como ha dicho en su pregunta- tendremos: $$u_{j}=\sum_{k=j}^{n}\left(-1\right)^{k-j}\binom{k}{j}a_{k}\tag1$$

Hasta ahora sólo he esbozado el montaje y ahora es el momento de encontrar la prueba combinatoria combinatoria de esto.

---

Lema : Si $S$ es un conjunto finito y no vacío entonces: $$|\{T\in\mathcal P(S)\mid |T|\text{ is odd}\}|=|\{T\in\mathcal P(S)\mid |T|\text{ is even}\}|$$

Prueba : Sencillo.

---

Teorema : Para todo número entero no negativo $j$ que tenemos: $$\mathbf{1}_{U_{j}}+\sum_{J\subseteq I\wedge\left|J\right|-j\text{ is odd}}\binom{\left|J\right|}{j}\mathbf{1}_{A_{J}}=\sum_{J\subseteq I\wedge\left|J\right|-j\text{ is even}}\binom{\left|J\right|}{j}\mathbf{1}_{A_{J}}$$

---

Antes de demostrar el teorema, veamos su impacto.

Si alguna medida $\mu$ y se trata de conjuntos medibles entonces la integración en ambos lados da como resultado $$\mu\left(U_{j}\right)+\sum_{J\subseteq I\wedge\left|J\right|-j\text{ is odd}}\binom{\left|J\right|}{j}\mu\left(A_{J}\right)=\sum_{J\subseteq I\wedge\left|J\right|-j\text{ is even}}\binom{\left|J\right|}{j}\mu\left(A_{J}\right)$$ Si tomamos la medida de conteo entonces automáticamente los conjuntos son medibles y a primera mano encontramos $$u_{j}+\sum_{k=j\wedge k-j\text{ is odd}}^{n}\binom{k}{j}a_{k}=\sum_{k=j\wedge k-j\text{ is even}}^{n}\binom{k}{j}a_{k}$$ donde $a_{k}$ y $u_{j}$ se definen como arriba.

Si además el $a_{k}$ son finitos, entonces podemos restar sin problemas para llegar a $$u_{j}=\sum_{k=j}^{n}\left(-1\right)^{k-j}\binom{k}{j}a_{k}\tag1$$

Así que $(1)$ se deduce inmediatamente del teorema y no es más que que un caso especial.

Sorprendentemente el teorema no es difícil de demostrar y lo único esencial que se necesita para ello es el lema.

---

Prueba :

Dejemos que $x\in X$ .

Entonces basta con demostrar que sustituyendo $x$ en ambos lados da resultados iguales. Por eso, déjalo: $$I_{x}:=\left\{ i\in I\mid x\in A_{i}\right\} $$ y discernir los siguientes casos:

$\left|I_{x}\right|<j$ entonces encontramos $0+0=0$ en el lado izquierdo y $0$ en el RHS.

$\left|I_{x}\right|=j$ entonces encontramos $1+0=1$ en el lado izquierdo y $1$ en el RHS.

$\left|I_{x}\right|>j$ entonces encontramos: $$0+\sum_{J\subseteq I_{x}\wedge\left|J\right|-j\text{ is odd}}\binom{\left|J\right|}{j}\binom{\left|I_{x}\right|}{\left|J\right|}=\binom{\left|I_{x}\right|}{j}\sum_{J\subseteq I_{x}\wedge\left|J\right|-j\text{ is odd}}\binom{\left|I_{x}\right|-j}{\left|J\right|-j}$$ en el LHS y: $$\binom{\left|I_{x}\right|}{j}\sum_{J\subseteq I_{x}\wedge\left|J\right|-j\text{ is even}}\binom{\left|I_{x}\right|-j}{\left|J\right|-j}$$ en el RHS.

El factor $\binom{\left|I_{x}\right|}{j}$ en ambos lados puede ser despojado y lo que queda es exactamente la afirmación verdadera de que el número de subconjuntos de un conjunto que tiene la cardinalidad finita $\left|I_{x}\right|-j>0$ con cardinalidad impar es igual al número de subconjuntos con cardinalidad par. Así que el contenido del lema.

Esto completa la prueba.

---

Esta es una prueba combinatoria no muy difícil de lo que usted llama el versión general de inclusión/exclusión y se basa en no más de un lema muy simple.