Principio de inclusión-exclusión

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.

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 A₁, ..., A_n, temos a identidade

$\left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}|A_{i}|-\sum _{1\leqslant i<j\leqslant n}|A_{i}\cap A_{j}|+\sum _{1\leqslant i<j<k\leqslant n}|A_{i}\cap A_{j}\cap A_{k}|-\cdots +(-1)^{n+1}\left|A_{1}\cap \cdots \cap A_{n}\right|.$

 

 

 

 

(1)

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}<\cdots <i_{k}\leqslant n}|A_{i_{1}}\cap \cdots \cap A_{i_{k}}|\right)$

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 S un conxunto universal finito que contén todos os A_i e sendo ${\bar {A_{i}}}$ o complemento de A_i en S, 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<j\leqslant n}|A_{i}\cap A_{j}|-\cdots +(-1)^{n}|A_{1}\cap \cdots \cap A_{n}|.$

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}<m_{2}\leqslant n}|A_{m_{1}}\cap A_{m_{2}}|+\cdots +(-1)^{p-1}\sum _{1\leqslant m_{1}<\cdots <m_{p}\leqslant n}|A_{m_{1}}\cap \cdots \cap A_{m_{p}}|+\cdots$

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₁ , ... , 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 ${\textstyle {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{aligned}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{aligned}}$

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 + 1 termos da expansión de Taylor de e⁻¹. Así, a probabilidade de colocar correctamente unha carta barallada aleatoriamente é de aproximadamente e^-1 ou 37%.

En probabilidade

En probabilidade, para os eventos A₁, ... , A_n nun espazo de probabilidade $(\Omega ,{\mathcal {F}},\mathbb {P} )$, o principio de inclusión-exclusión pasa a ser para n = 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 = 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<j}\mathbb {P} (A_{i}\cap A_{j})+\sum _{i<j<k}\mathbb {P} (A_{i}\cap A_{j}\cap A_{k})+\cdots +(-1)^{n-1}\sum _{i<...<n}\mathbb {P} \left(\bigcap _{i=1}^{n}A_{i}\right),$

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 A_i 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 A_k 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 P_i como "a función perde o elemento i en B " (i non está na imaxe da función), o principio de inclusión–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₁, A₂, ... , A_k, e as propiedades P_i que significan que a partición ten a caixa A_i 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 P_i como que un número en S é divisíbel polo número primo p_i, 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<j\leqslant r}{\frac {n}{p_{i}p_{j}}}-\cdots =n\prod _{i=1}^{r}\left(1-{\frac {1}{p_{i}}}\right).$

Método da hipérbola de Dirichlet

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).$

Véxase tamén

Bibliografía

• Allenby, R.B.J.T.; Slomson, Alan (2010). How to Count: An Introduction to Combinatorics. Discrete Mathematics and Its Applications (2 ed.). CRC Press. pp. 51–60. ISBN 9781420082609. 
• Björklund, A.; Husfeldt, T.; Koivisto, M. (2009). Set partitioning via inclusion–exclusion. SIAM Journal on Computing 39. pp. 546–563. doi:10.1137/070683933. 
• Brualdi, Richard A. (2010). Introductory Combinatorics (5th ed.). Prentice–Hall. ISBN 9780136020400. 
• Cameron, Peter J. (1994). Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press. ISBN 0-521-45761-0. 
• Fernández, Roberto; Fröhlich, Jürg; Alan D., Sokal (1992). Random Walks, Critical Phenomena, and Triviality in Quantum Field Theory. Texts an Monographs in Physics. Berlin: Springer-Verlag. pp. xviii+444. ISBN 3-540-54358-9. MR 1219313. Zbl 0761.60061. 
• Graham, R.L.; Grötschel, M.; Lovász, L. (1995). Hand Book of Combinatorics (volume-2). MIT Press – North Holland. ISBN 9780262071710. 
• Gross, Jonathan L. (2008). Combinatorial Methods with Computer Applications. Chapman&Hall/CRC. ISBN 9781584887430. 
• "Inclusion-and-exclusion principle". Encyclopedia of Mathematics. EMS Press. 2001 [1994]. 
• Mazur, David R. (2010). Combinatorics A Guided Tour. The Mathematical Association of America. ISBN 9780883857625. 
• Roberts, Fred S.; Tesman, Barry (2009). Applied Combinatorics (2nd ed.). CRC Press. ISBN 9781420099829. 
• Stanley, Richard P. (1986). Enumerative Combinatorics Volume I. Wadsworth & Brooks/Cole. ISBN 0534065465. 
• van Lint, J.H.; Wilson, R.M. (1992). A Course in Combinatorics. Cambridge University Press. ISBN 0521422604. 

Outros artigos

• Desigualdade de Boole
• Principios de combinatoria
• Problema do colar de xoias
• Principio do pombal
• Fórmula de Schuette–Nesbitt