Principio de Inclusión-Exclusión

En lo personal, se trata del tema más interesante y práctico de la asignatura, así que pónganse cómodos y a disfrutar xD. Avisar que es estrictamente necesario haber trabajado combinatoria básica para entender este punto en su máximo esplendor.

Sobre un conjunto inicial $S$ de cardinal $N$, definimos una colección de condiciones $c_i, i=1,...,t$; posibles en algunos de los elementos de $S$. A la hora de contar cuántos de los elementos de $S$ verifican dichas condiciones, por separado o conjuntamente, se introducen las notaciones:

• $N(c_i)$ denota el número de elementos de $S$ que verifican la condición $c_i$. De la misma forma, $N(\bar{c_i}) \equiv \bar{N}(c_i)$ denota la cantidad de elementos de $S$ que no verifican la condición $c_i$. Es decir: $\bar{c_i}$ es la condición complementaria a $c_i$.
• $N \left (c_{i_1} c_{i_2} \dotsb c_{i_k} \right )$ es la cantidad de elementos de $S$ que verifican cada una de las condiciones $i_1, i_2, ..., i_k$.
• $E_m$ es el número de elementos de $S$ que verifica exactamente $m$ de las condiciones definidas.
• $L_m$ trabaja el número de elementos que verifica al menos $m$ de las condiciones.

Surgen algunos resultados relevantes acerca del cálculo de $\bar{N}, E_m, L_m$. En particular:

(Cálculo de $\bar{N}$) Siendo $c_i, i=1,...,t$ condiciones sobre el conjunto $S$, se tiene: $$\bar{N}(c_1 \dotsb c_t) = N- \sum_{i=1} ^t N(c_i) + \sum_{1\leq i < j \leq t} N(c_i c_j) - \sum_{1\leq i<j<k \leq t} N(c_i c_j c_k) + \dotsb + (-1)^t N(c_1 \dotsb c_t)$$

Demostración: Veamos que ambos miembros cuentan cada elemento de $S$ el mismo número de veces. Un elemento que no cumple ninguna de las $t$ condiciones, se cuenta una vez en $\bar{N}$, otra en $N$ y cero en el resto. Por el contrario, si un genérico en $S$ verifica $r\in \{ 1,...,t \}$ condiciones, se cuenta cero veces en $\bar{N}$, 1 vez en $N$, y:

• $r$ veces en la primera suma.
• $\binom{r}{2}$ veces en la segunda suma.
• $\binom{r}{3}$ en la tercera...

Así hasta llegar a $\binom{r}{r} = 1$ vez en la suma que involucra $r$ condiciones; y cero en adelante. Teniendo en cuenta los signos de la igualdad propuesta, en el miembro derecho se cuenta un total de:

$$1 - \binom{r}{1} + \binom{r}{2} + \dotsb + (-1)^r \binom{r}{r} = \sum_{j=0}^{r} \binom{r}{j} (-1)^j = (1+(-1))^r = 0 \text{ veces}$$

, concluyendo así la prueba.

$\square$

De aquí en adenlante, conviene hacer uso de la notación estandarizada:

$$S_k = \sum_{1\leq i_1  < i_2 < \dotsb < i_k \leq t} N(c_{i_1} \dotsb c_{i_k}) \quad 1\leq k \leq t$$

(Cálculo de $E_m$) Siendo $c_i, i=1,...,t$ condiciones sobre el conjunto $S$, se tiene: $$\begin{eqnarray} E_m & = & S_{m} - \binom{m+1}{1} S_{m+1} + \binom{m+2}{2} S_{m+2} + \dotsb + (-1)^{t-m} \binom{t}{t-m} S_t = \\  & = & \sum_{j=m} ^{t} (-1)^{j-m} \binom{j}{j-m} S_j \end{eqnarray}$$

Demostración: Seguimos la misma estrategia de la prueba anterior. Si un elemento de $S$ no verifica al menos $m$ condiciones de las establecidas, no se cuenta en ninguna parte. Si cumple exactamente $m$, se cuenta una vez en $E_m, S_m$ y cero veces en el resto. Si verifica más de $m$ condiciones, pongamos $r\in \{1+m,...,t \}$, no se cuenta en $E_m$, y:

• Se cuenta $\binom{r}{m}$ veces en $S_m$.
• $\binom{r}{m+1}$ veces en $S_{m+1}$...

Así hasta llegar a contarse $\binom{r}{r-1}$ veces en $S_{r-1}, 1$ vez en $S_r$ y cero en adelante. Se cuenta un total de:

$$\binom{r}{m} - \binom{r}{m+1} \binom{m+1}{1} + \binom{r}{m+2} \binom{m+2}{2} + \dotsb + (-1)^{r-m} \binom{r}{r} \binom{r}{r-m}$$

veces en el miembro derecho. Según el tercer problema del artículo del Teorema Multinomial, la anterior suma es nula para todo $r\in \{1+m,...,t \}$. Se concluye así la prueba.

$\square$

(Cálculo de $L_m$) Siendo $c_i, i=1,...,t$ condiciones sobre el conjunto $S$, se tiene: $$L_m = S_m - \binom{m}{m-1}S_{m+1} +\dotsb + (-1)^{t-m} \binom{t-1}{m-1} S_t = \sum_{j=m} ^t (-1)^{j-m} \binom{j-1}{m-1}S_j$$

Demostración: Veamos una serie de propiedades antes de realizar la prueba:

• Ya que hay un total de $t$ condiciones, cumplir al menos $t$ de ellas es lo mismo que cumplir exactamente $t$. Luego $L_t = E_t$. De la fórmula de $E_t$, se tiene: $E_t = S_t$, y como tal: $\boxed{L_t = E_t = S_t}$.
• Cuando un elemento de $S$ verifica al menos $m$ condiciones, verifica exactamente $m$ condiciones o al menos $m+1$; siendo $m=1,...,t-1$. Así: $\boxed{L_m = E_m + L_{m+1}}$.
• A partir de las dos propiedades anteriores, uno deduce: $$L_{t-1} = E_{t-1} + L_t = (S_{t-1} -t S_t) + S_t = S_{t-1} - \binom{t-1}{t-2} S_t$$

Estamos ya preparados para realizar la prueba por inducción inversa. Inicialmente, en los casos finales, hemos comprobado la fórmula para $m=t, t-1$. Suponiendo como hipótesis inductiva:

$$L_{m+1} = S_{m+1} - \binom{m+1}{m}S_{m+2} +\dotsb + (-1)^{t-m-1} \binom{t-2}{m} S_t = \sum_{j=m+1} ^t (-1)^{j-m-1} \binom{j-1}{m}S_j$$ , tenemos:

$$\begin{eqnarray} L_{m} & = & E_m + L_{m+1} = \sum_{j=m} ^{t} (-1)^{j-m} \binom{j}{j-m} S_j + \sum_{k=m+1} ^t (-1)^{k-m-1} \binom{k-1}{m}S_k = \\ & = & S_m + \sum_{j=m+1} ^t (-1)^{j-m} \left [ \binom{j}{j-m} - \binom{j-1}{m} \right ] S_j = \\ & = & S_m + \sum_{j=m+1} ^t (-1)^{j-m} \binom{j-1}{m-1} S_j = \sum_{j=m} ^t (-1)^{j-m} \binom{j-1}{m-1} S_j \quad :)   \end{eqnarray}$$

, donde hemos usado:

$$\binom{j}{j-m} - \binom{j-1}{m} = \frac{j!}{(j-m)! m!} - \frac{(j-1)!}{m! (j-1-m)!} = \frac{j! -(j-1)! (j-m)}{(j-m)! m!} = \underset{=\binom{j-1}{m-1}}{\underbrace{\frac{(j-1)!}{(j-m)! (m-1)!}}}$$

$\square$

EJERCICIOS PROPUESTOS

1. Encontrar la cantidad de múltiplos de $3,5$ ó (inclusivo) $7$ en el conjunto $\{ 1,2,...,500 \}$.
2. La profesora asigna 12 parejas para la realización de un trabajo de literatura. Observa que ninguna pareja parece ser eficaz trabajando, y quiere rehacer las parejas consiguiendo que todas sean distintas a las originales. ¿Cuántas formas tiene de hacerlo?. Solución.
3. Determinar el número de formas de colocar las letras de "mamasota" de forma que haya: i) 2 pares de letras repetidas consecutivamente. ii) Ninguna letra repetida consecutivamente. Solución.
4. ¿Cuántas funciones inyectivas hay de $\{1,...,10 \}$ a $\{a,b,c,d \}$? ¿Y sobreyectivas?. ¿Cuántas funciones crecientes hay de $\{ 1,...,5 \}$ a $\{ 0,1,...,9 \}$?. Solución.
5. (DE EXAMEN) Una empresa bancaria quiere renovar la flota de sillas ergonómicas en sus sedes ubicadas en las cuatro capitales de provincia siguientes: Albacete, Badajoz, Cuenca y Teruel. Para ello quiere distribuir 200 sillas ergonómicas idénticas entre estas ciudades. Calcular el número de distribuciones posibles de estas sillas entre dichas ciudades para cada uno de los siguientes supuestos: a) No hay limitación sobre el número de sillas que puede asignarse a cada ciudad. b) Al menos 40 sillas, y como máximo 60 sillas, deben recibirse en cada ciudad. c) En Albacete deben repartirse al menos 50 sillas, pero no más de 70 sillas; la ciudad de Badajoz debe recibir al menos 35 sillas, pero en ningún caso debe alcanzar las 90 sillas; a Cuenca deben llegar más de 25 sillas y como máximo 80 sillas; y la ciudad de Teruel debe recibir como mínimo 45 sillas y como máximo 65 sillas. d) La ciudad de Teruel debe recibir exactamente 80 sillas.
6. (DE EXAMEN) Se quiere organizar una competición de un deporte específico, entre los mejores equipos del continente. Para ello, se deciden aleatoriamente qué enfrentamientos se llevan a cabo y cuáles no. a) ¿Cuántas competiciones de este tipo pueden organizarse con los 50 mejores equipos del continente? b) ¿Cuántas competiciones de este tipo pueden organizarse con los 10 mejores equipos del continente? c) ¿En cuántas de las competiciones calculadas en (b), todos y cada uno de esos 10 equipos juega al menos un partido? d) (d1) ¿En cuántas de las competiciones calculadas en (b), el número de equipos que no juega ningún partido es menor que 5? (d2) ¿Y menor que 3? e) (e1) Se fija el equipo 1. ¿En cuántas de las competiciones calculadas en (b) participa dicho equipo jugando al menos un partido? (e2) Se fijan los equipos 1 y 2. ¿En cuántas de las competiciones calculadas en (b) participan ambos equipos jugando cada uno de ellos al menos un partido?