Indução. Contagem básica e contagem por inclusão-exclusão, recorrência (números de Catalan) e funções geradoras. Somatórios, números binomiais, notação assintótica e estimativas. Contagem Dupla (Teorema de Sperner + Problema de Littlewood-Offord). Grafos (noções básicas, árvores, ciclos, grafos bipartidos, emparelhamentos, grafos Eulerianos e Hamiltonianos, grafos planares). Introdução à teoria extremal de grafos (Mantel, Turán e número extremal do ciclo de tamanho 4). Introdução à teoria de Ramsey (festa com 6 pessoas, cota superior para números de Ramsey). Introdução à probabilidade discreta e ao método probabilístico (cota inferior para o número de Ramsey).

Informações Básicas:

• Carga horária: 60 horas;
• Pré-requisito: Não se aplica.

Bibliografia Obrigatória:

• Matousek, J; Nesetril, J, Invitation to Discrete Mathematics, Oxford University Press, 2nd edition, 2008;
• Bona, M; A walk Through Combinatorics: An introduction to Enumeration and Graph Theory, WSPC, 4th edition, 2016;
• Graham, R; Knuth, D; Patashnik, O.;Matemática Concreta. Fundamentos para a Ciência da Computação. Livros Técnicos e Científicos, 1995.

Bibliografia Complementar:

• Cameron, P; Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, 1st edition, 1994;
• Diestel, R.; Graph Theory, Springer, 5th edition, 2017;
• van Lint, J. H; Wilson, R. M; A Course in Combinatorics, Cambridge University Press, 2nd edition, 2001;
• Bollobás, B; Modern Graph Theory; Springer, 1st edition, 1998;
• Bondy, J.A.; Murty, U. S. R; Graph theory; Springer, 2008.