O princípio da inclusão-exclusão e o cálculo de permanentes

Abstract

Neste artigo revisamos o princípio da inclusão-exclusão (PIE) sob os pontos de vista conjuntista e algébrico e discutimos sua aplicação ao cálculo de permanentes, um assunto que normalmente não é abordado em cursos de graduação. A apresentação procura ser rigorosa porém elementar e acessível a alunos dos anos iniciais de cursos de licenciatura ou bacharelado em matemática, ciências e engenharias, exigindo somente familiaridade com notação de conjuntos, aritmética e álgebra de matrizes. No tratamento do cálculo de permanentes, apresentamos o algoritmo de Ryser, um dos desenvolvimentos mais espetaculares na abordagem de problemas combinatoriais difíceis, cuja complexidade algorítmica discutimos brevemente. O artigo inclui exemplos, notas complementares e um programa em Python que implementa o algoritmo de Ryser usando códigos de Gray para o cálculo de permanentes, juntamente com sua discussão.

Keywords

• matemática discreta
• análise combinatória
• partição de conjuntos
• algoritmo de Ryser
• problemas #P-completos