Ementa/Descrição: |
O Princípio de indução. Algumas ferramentas da combinatória: Princípio
multiplicativo da contagem, Inclusão-Exclusão e Princípio da Casa dos
Pombos. Elementos de combinatória: permutações, anagramas, arranjos e
combinações. Coeficientes binomiais e o Triângulo de Pascal: o Teorema
Binomial, o Triângulo de Pascal e as identidades no Triângulo de Pascal.Números de Fibonacci: definição, identidades e fórmula para os números de
Fibonacci. Grafos: grau de um vértice, caminhos, ciclos, conectividade,
passeios eulerianos e ciclos hamiltonianos. Árvores: definição mediante
grafos, caracterização, crescimento de árvores, contagem de árvores e
árvores não rotuladas e árvore ótima. Emparelhamentos em grafos: grafos
bipartidos, Teorema do Emparelhamento, emparelhamento perfeito.
Combinatória em Geometria. Fórmula de Euler. Coloração de mapas e
grafos: coloração com duas cores, coloração com 3 cores. Teorema das
Quatro Cores. |