masterThesis
Teoria enumerativa de Pólya
Autor
CASSIMIRO, Débora Virginia Ramos Barbosa
Institución
Resumen
CASSIMIRO, Débora Virginia Ramos Barbosa, também é conhecida em citações bibliográficas por: BARBOSA, Débora Virginia Ramos Nesta dissertação, estamos preocupados com o problema de contar objetos matemáticos levando-se em conta as suas simetrias. Dois teoremas importantes na Área de Análise Combinatória são o Lema de Burnside e o Teorema da Enumeração de Pólya. Ambos fornecem uma fórmula matemática que permite calcular o número de objetos matemáticos distintos levando-se em conta as simetrias. O primeiro destes utiliza o conceito de órbitas para contar o número de objetos matemáticos. Embora o Lema de Burnside seja conceitualmente mais simples, ele apresenta a desvantagem de ter um alto custo computacional. O Teorema de Pólya utiliza o conceito de índice de ciclos e não só reduz a quantidade de cálculos necessária como também permite a resolução de problemas mais complexos. Além disso, o conceito de índice de ciclos nos trás informação sobre cada padrão distinto, o que permite uma descrição mais completa do problema. A partir de definições básicas tomadas da Teoria dos Grupos, nós fornecemos uma apresentação da teoria que leva a demonstração do Teorema de Pólya. Concluímos com diversas aplicações desta teoria à diferentes tipos de problemas para ilustrar este conceito. CNPq In this dissertation, we are concerned with the problem of counting mathematical objects with regards to symmetry. Two major theorems in Combinatorics are Burnside’s Lemma and Pólya’s Enumeration Theorem. Both theorems yield a formula that allows one to compute the number of distinct mathematical objects with regards to symmetry. Although Burnside’s Lemma is conceptually simpler, it presents a disadvantage in that it has a high computational cost. Pólya’s Enumeration Theorem uses the concept of cycle index and not only reduces the required amount of calculations but it also allows for more complex problems to be solved. Moreover, the concept of cycle index brings us information on each distinct pattern, which allows for a more complete description of the problem. Building up from basic definitions taken from Group Theory, a presentation of the theory leading up to the demonstration of Pólya’s Enumeration Theorem is given. We conclude with several applications of this theory in different types of problems to illustrate these concepts.