Principio de inclusión-exclusión

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



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



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
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



ou



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   o complemento de  en , polas leis de De Morgan  temos



 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 Am, 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, é



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



Cada valor  representa o conxunto de resultados de barallar que teñen polo menos p valores m1 , ... , 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 . 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  termos iguais na suma p-ésima (ver combinación).



 é 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:



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



que é un truncamento a n + 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 A1, ... , An nun espazo de probabilidade , o principio de inclusión-exclusión pasa a ser para n = 2



para n = 3



e en xeral



que se pode escribir en forma pechada como



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



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  o complemento de Ak con respecto a algún conxunto universal A tal que  para cada k. Así temos



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–exclusión dá o número de funcións seobrexectivas entre A e B como: 



 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), A1, A2, ... , 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: 



 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 é:



Entón, 



 Método da hipérbola de Dirichlet 
miniatura| Un exemplo do método da hipérbola de Dirichlet con  e 
O método da hipérbola de Dirichlet reexpresa a suma dunha función multiplicativa  seleccionando unha convolución de Dirichlet adecuada , recoñecendo que a suma



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


 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

Categoría:Probabilidade
Categoría:Combinatoria
Categoría:Wikipedia:Páxinas con traducións non revisadas