Principio de inclusión-exclusión

[miniatura| [Diagrama de Venn que mostra a unión dos conxuntos *A* e *B* como todo o que non está en branco]]
En combinatoria, o **principio de inclusión-exclusión** é unha técnica de contaxe que xeneraliza o método familiar de obter o número de elementos na unión de dous conxuntos finitos; expresado simbolicamente como

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

onde *A* e *B* son dous conxuntos finitos e |*S*| indica a cardinalidade dun conxunto *S* (número de elementos do conxunto). A fórmula expresa o feito de que na suma  algúns elementos poden ser contados dúas veces. Os elementos de dobre conta son os que están na intersección dos dous conxuntos e o número é corrixido restando o tamaño da intersección.

O principio de inclusión-exclusión, é unha xeneralización do caso de dous conxuntos, sendo quizais máis claramente visto no caso de tres conxuntos. Así, para os conxuntos *A*, *B* e *C,* vén dado por

: |A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

Esta fórmula pódese verificar contando cantas veces se inclúe cada rexión da figura do diagrama de Venn na parte dereita da fórmula. Neste caso, ao eliminar as contribucións de elementos supercontados, o número de elementos na intersección mutua dos tres conxuntos réstase con demasiada frecuencia, polo que hai que engadir de novo para obter o total correcto.
miniatura| Inclusión-exclusión ilustrada por un diagrama de Venn para tres conxuntos

## Fórmula 
Na súa fórmula xeral, o principio de inclusión-exclusión estabelece que para os conxuntos finitos , temos a identidade{{Bloque numerado|:|\left|\bigcup_{i=1}^n A_i\right| = \sum_{i=1}^n |A_i| - \sum_{1 \leqslant i |}}
[miniatura| Cada termo da fórmula de inclusión-exclusión corrixe gradualmente a contaxe ata que finalmente cada parte do [diagrama de Venn cóntase exactamente unha vez.]]
Isto pódese escribir de forma compacta como

: \left|\bigcup_{i=1}^n A_i\right| = \sum_{k=1}^n (-1)^{k+1} \left( \sum_{1 \leqslant i_1 

ou

: \left| \bigcup_{i=1}^n A_i\right| = \sum_{\emptyset\neq J\subseteq\{1,\ldots,n\}}(-1)^{|J|+1} \left |\bigcap_{j\in J} A_j\right|.

Nas aplicacións é habitual ver o principio expresado na súa forma complementaria. É dicir,sebdi  un conxunto universal finito que contén todos os  e sendo \bar{A_i}  o complemento de  en , polas leis de De Morgan  temos

: \left|\bigcap_{i=1}^n \bar{A_i}\right| = \left|S - \bigcup_{i=1}^n A_i \right| =|S| - \sum_{i=1}^n |A_i| + \sum_{1 \leqslant i 

## Exemplos 
### Contando desarranxos 
Supoñamos que hai unha baralla de *n* cartas numeradas dende 1 a *n*. Supoña que unha carta numerada *m* está na posición correcta se é a *m-ésima* carta da baralla. De cantas formas, *W*, pódense barallar as cartas con polo menos 1 carta na posición correcta?

Comezamos definindo o conxunto *A**m*, que son todas as ordenacións de cartas coa carta *m-ésima* correcta. Entón, o número de ordenacións, *W*, con *polo menos* unha carta na posición correcta, *m*, é

: W = \left|\bigcup_{m=1}^n A_m\right|.

Aplicando o principio de inclusión-exclusión,

: W = \sum_{m_1=1}^n |A_{m_1}| - \sum_{1 \leqslant m_1 

Cada valor A_{m_1} \cap \cdots \cap A_{m_p} representa o conxunto de resultados de barallar que teñen polo menos *p* valores *m*1 , ... , *m p* na posición correcta. Teña en conta que o número de mesturas con polo menos *p* valores correctos só depende de *p*, non dos valores particulares de m. Por exemplo, o número de mesturas que teñen as cartas,  1, 3, e 17 na posición correcta é o mesmo que o número de cartas que teñen as cartas 2, 5 e 13 nas posicións correctas. Só importa que das *n* cartas, 3 resultaron baralladas ficando na posición correcta. Así hai {n \choose p} termos iguais na suma *p-ésima* (ver combinación).

: W = {n \choose 1} |A_1| - {n \choose 2} |A_1 \cap A_2| + \cdots + (-1)^{p-1} {n \choose p} |A_1 \cap \cdots \cap A_p| + \cdots

|A_1 \cap \cdots \cap A_p| é o número de ordenacións que teñen *p* elementos na posición correcta, que é igual ao número de formas de ordenar os restantes *n* − *p* elementos ou (*n* − *p* )!. Así, finalmente, obtemos:

: \begin{align}
W &= {n \choose 1} (n-1)! - {n \choose 2} (n-2)! + \cdots + (-1)^{p-1} {n \choose p} (n-p)! + \cdots\\
&= \sum_{p=1}^n (-1)^{p-1} {n \choose p} (n-p)! \\
&= \sum_{p=1}^n (-1)^{p-1} \frac{n!}{p!(n-p)!} (n-p)! \\
&= \sum_{p=1}^n (-1)^{p-1} \frac{n!}{p!}
\end{align}

Unha permutación na que *ningunha* carta está na posición correcta chámase desarranxo. Como *n*! é o número total de permutacións, a probabilidade *Q* de que unha mestura aleatoria produza un desarranxo vén dada por

: Q = 1 - \frac{W}{n!} = \sum_{p=0}^n \frac{(-1)^p}{p!}, 

que é un truncamento a *n*&nbsp;+&nbsp;1 termos da expansión de Taylor de *e*−1. Así, a probabilidade de colocar correctamente unha carta barallada aleatoriamente é de aproximadamente *e*-1 ou 37%.

## En probabilidade 
En probabilidade, para os eventos *A*1, ... , *A**n* nun espazo de probabilidade (\Omega,\mathcal{F},\mathbb{P}), o principio de inclusión-exclusión pasa a ser para *n*&nbsp;=&nbsp;2

: \mathbb{P}(A_1\cup A_2)=\mathbb{P}(A_1)+\mathbb{P}(A_2)-\mathbb{P}(A_1\cap A_2),

para *n*&nbsp;=&nbsp;3

: \mathbb{P}(A_1\cup A_2\cup A_3)=\mathbb{P}(A_1)+\mathbb{P}(A_2)+\mathbb{P}(A_3)-\mathbb{P}(A_1\cap A_2)-\mathbb{P}(A_1\cap A_3)-\mathbb{P}(A_2\cap A_3)+\mathbb{P}(A_1\cap A_2\cap A_3)

e en xeral

: \mathbb{P}\left(\bigcup_{i=1}^n A_i\right)=\sum_{i=1}^n \mathbb{P}(A_i) -\sum_{i

que se pode escribir en forma pechada como

: \mathbb{P}\left(\bigcup_{i=1}^n A_i\right)=\sum_{k=1}^n \left((-1)^{k-1}\sum_{I\subseteq\{1,\ldots,n\}\atop |I|=k} \mathbb{P}(A_I)\right),

onde a última suma percorre todos os subconxuntos *I* dos índices 1,... , *n* que conteñen exactamente *k* elementos, e

: A_I:=\bigcap_{i\in I} A_i

denota a intersección de todos aqueles *Ai* con índice en *I* .

## Aplicacións 
O principio de inclusión-exclusión é moi utilizado e só algunhas das súas aplicacións son mencionadas aquí.

### Contar desarranxos 
Unha aplicación ben coñecida do principio de inclusión-exclusión é o problema combinatorio de contar todos os desarranxos dun conxunto finito. O desarranxo dun conxunto *A* é unha bixección de *A* en si mesmo que non ten puntos fixos. A través do principio de inclusión–exclusión pódese demostrar que se a cardinalidade de *A* é *n*, entón o número de desarranxos é [*n*! / *e*], onde [*x*] indica o número enteiro máis próximo a *x*; como vimos no exemplo da parte superior.

### Contando as interseccións 
O principio de inclusión-exclusión, combinado coa lei de De Morgan, tamén se pode usar para contar a cardinalidade da intersección de conxuntos. Sexa \overline{A_k} o complemento de *Ak* con respecto a algún conxunto universal *A* tal que A_k \subseteq A para cada *k*. Así temos

: \bigcap_{i=1}^n A_i = \overline{\bigcup_{i=1}^n \overline{A_i}}

convertendo así o problema de atopar unha intersección no problema de atopar unha unión.

### Colorar grafos 
O principio de inclusión-exclusión constitúe a base dos algoritmos para unha serie de problemas de partición de grafos  NP-fortes, como a colorar grafos. 

Unha aplicación ben coñecida do principio é a construción do polinomio cromático dun grafo.

### Número de funcións sobrexectivas 
Dados os conxuntos finitos *A* e *B*, cantas funcións sobrexectivas  hai de *A* a *B* ? Sen ningunha perda de xeneralidade podemos tomar *A* = {1, ..., *k* } e *B* = {1, ..., *n* }, xa que só importan as cardinalidades dos conxuntos. Usando *S* como o conxunto de todas as funcións de *A* a *B* e definindo, para cada *i* en *B*, a propiedade *Pi* como "a función perde o elemento *i* en *B* " (*i* non está na imaxe da función), o principio de inclusión&#x2013;exclusión dá o número de funcións seobrexectivas entre *A* e *B* como: 

: \sum_{j=0}^{n} \binom{n}{j} (-1)^j (n-j)^k.

### Números de Stirling do segundo tipo 
Os números de Stirling do segundo tipo, *S* (*n*, *k*) contan o número de particións dun conxunto de *n* elementos en *k* subconxuntos non baleiros (*caixas* indistinguibles). Pódese obter unha fórmula explícita para eles aplicando o principio de inclusión-exclusión a un problema moi relacionado, é dicir, contando o número de particións dun *n*-conxunto en *k* caixas non baleiras pero distinguibles (subconxuntos ordenados non baleiros). Usando o conxunto universal que consiste en todas as particións do conxunto *n* en *k* caixas distinguibles (posiblemente baleiras), *A*1, *A*2, ... , *Ak*, e as propiedades *Pi* que significan que a partición ten a caixa *Ai* baleira, o principio de inclusión-exclusión dá unha resposta para o resultado relacionado. Dividindo por *k*! para eliminar a ordenación artificial dá o número de Stirling do segundo tipo: 

: S(n,k) = \frac{1}{k!}\sum_{t=0}^k (-1)^t \binom k t (k-t)^n.

### Función fi de Euler 
A función totiente de Euler ou fi de Euler, *φ* (*n*) é unha función aritmética que conta o número de enteiros positivos inferiores ou iguais a *n* que son relativamente primos con *n*. É dicir, se *n* é un número enteiro positivo, entón φ(*n*) é o número de enteiros *k* no rango 1 ≤ *k* ≤ *n* que non teñen ningún factor común con *n* distinto de 1. O principio de inclusión-exclusión úsase para obter unha fórmula para φ(*n*). Sexa *S* o conxunto {1, ..., *n* } e definimos a propiedade *Pi* como que un número en *S* é divisíbel polo número primo *pi*, para 1 ≤ *i* ≤ *r*, onde a factorización prima de *n é:*

: n = p_1^{a_1} p_2^{a_2} \cdots p_r^{a_r}.

Entón, 

: \varphi(n) = n - \sum_{i=1}^r \frac{n}{p_i} + \sum_{1 \leqslant i 

### Método da hipérbola de Dirichlet 
miniatura| Un exemplo do método da hipérbola de Dirichlet con n = 10,a \approx 2.7, e b \approx 3.7.
O método da hipérbola de Dirichlet reexpresa a suma dunha función multiplicativa f(n) seleccionando unha convolución de Dirichlet adecuada f = g \ast h, recoñecendo que a suma

: F(n) = \sum_{k=1}^n f(k) = \sum_{k=1}^n \sum_{xy=k}^{} g(x) h(y)

pode ser reorganizado como unha suma sobre os puntos da retícula nunha rexión limitada por x \geq 1, y \geq 1, e xy \leq n, dividindo esta rexión en dúas subrexións superpostas e, finalmente, utilizando o principio de inclusión-exclusión para concluír que

: F(n) = \sum_{k=1}^n f(k)
= \sum_{k=1}^n \sum_{xy=k}^{} g(x)h(y)
= \sum_{x=1}^a \sum_{y=1}^{n/x} g(x)h(y) + \sum_{y=1}^b \sum_{x=1}^{n/y} g(x)h(y) - \sum_{x=1}^a \sum_{y=1}^b g(x)h(y).
## Notas 
## Véxase tamén 
### Bibliografía 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 

### Outros artigos 
* Desigualdade de Boole
* Principios de combinatoria
* Problema do colar de xoias
* Principio do pombal
* Fórmula de Schuette–Nesbitt