Princípio da Inclusão-Exclusão
O princípio da inclusão-exclusão contabiliza o tamanho de uma união de conjuntos adicionando e subtraindo alternadamente os tamanhos de suas interseções.
Definition
Uma identidade de contagem que afirma que a cardinalidade de uma união de conjuntos finitos é igual à soma alternada das cardinalidades de todas as suas interseções, consideradas para cada subcoleção não vazia.
Scope
Este tópico apresenta a fórmula de inclusão-exclusão e suas aplicações na contagem de objetos que evitam uma lista de propriedades proibidas: desarranjos, sobrejeções, a função totiente de Euler e o número de inteiros coprimos a um dado número. Ele introduz a perspectiva do crivo e a generalização da função de Möbius sobre conjuntos parcialmente ordenados, o que situa o princípio em um contexto algébrico mais amplo.
Core questions
- Quantos elementos satisfazem pelo menos uma de várias condições sobrepostas?
- Como se pode contar objetos que evitam todas as propriedades de um conjunto de propriedades proibidas?
- Como as contagens de desarranjos e sobrejeções decorrem do princípio?
- Como a função de Möbius em um poset generaliza a inclusão-exclusão?
Key concepts
- União de conjuntos sobrepostos
- Método do crivo
- Desarranjos via inclusão-exclusão
- Contagem de sobrejeções
- Função totiente de Euler
- Função de Möbius em posets
Key theories
- Fórmula de inclusão-exclusão
- A cardinalidade de uma união de conjuntos A_1 a A_n é igual à soma dos tamanhos dos conjuntos individuais menos as interseções de pares, mais as interseções de trios, e assim por diante, corrigindo sistematicamente a contagem excessiva de elementos compartilhados.
- Inversão de Möbius em posets
- A generalização de Stanley baseada na teoria de posets substitui os sinais alternados da inclusão-exclusão pela função de Möbius de um conjunto parcialmente ordenado, unificando o princípio com fórmulas de inversão da teoria dos números e da teoria de reticulados.
Clinical relevance
A ideia do crivo generaliza-se para a teoria dos números (o crivo de Eratóstenes e crivos analíticos), probabilidade (as desigualdades de Bonferroni que limitam as probabilidades de união) e análise de confiabilidade de sistemas com modos de falha sobrepostos.
History
Essencialmente formulado por de Moivre e Sylvester, o princípio foi inserido em uma teoria geral das funções de Möbius em conjuntos parcialmente ordenados por Rota em 1964, um marco da combinatória moderna.
Key figures
- Abraham de Moivre
- Gian-Carlo Rota
Related topics
Seminal works
- stanley2011
Frequently asked questions
- Por que os sinais são alternados?
- Elementos que pertencem a vários dos conjuntos são adicionados muitas vezes; subtrair as interseções de pares corrige excessivamente, então as interseções de trios são adicionadas de volta, produzindo o padrão alternado que contabiliza cada elemento exatamente uma vez.
- Qual é a conexão com a função de Möbius?
- A inclusão-exclusão é o caso especial da inversão de Möbius na rede booleana de subconjuntos, onde a função de Möbius assume valores de mais ou menos um.