1

2018-2019

01001168

Mathematics

Portuguese

Face-to-face

SEMESTRIAL

7.5

Compulsory

1st Cycle Studies

Good knowledge of the combinatorics taught in High School Mathematics. Familiarity with mathematical induction, results in elementary number theory and basic mathematical concepts (logic and proof, set, relation, function) taught in Number Theory and Infinitesimal Analysis I courses.

TP classes are expository and include examples to clarify and motivate concepts, and exercises for applying the acquired knowledge. Problem solving by the students is fundamental in the learning process. Optional challenging problems are also proposed.

During the semester, students may use tutorial time to clarify their difficulties and in training their knowledge in problem solving.

This is an introductory course on combinatorial analysis: enumerative combinatorics and graph theory. Combinatorics is a branch of mathematics that applies to problems ranging from card games to algebra and to the internet. The goal is to provide the students with the basic knowledge in this area.

The course aims at developing the following skills: generalization, abstraction, creativity and calculus capacity; ability to formulate and solve problems; conception of mathematical models and their use on counting and to solve problems of real life; logical reasoning; independent thinking; research, imagination and independent learning.

Topics on combinatorics. Pigeonhole principle, mathematical induction and recurrence. Elementary counting principles. Subsets, binomial coefficients. Multisets, compositions, multinomial coefficients. Integer partitions. Set partitions. Permutations and cycles in permutations. Stirling and Bell numbers. Inclusion-exclusion principle. Generating functions and recurence relations.

Topics on graphs. Graphs, digraphs and networks: basic definitions, connectivity, structure, trees, Euler tours, Hamilton cycles, planarity, fundamental indices. Subgraphs and minors. Some important algorithms (as DFS - depth first search, BFS - breadth first search, Kruskal, Warshall, of the shortest path, of flows).

João Eduardo da Silveira Gouveia

Assessment

*Exam (100%) or Midterm exam(80%) + Test (20%): 100.0%*

Class Notes O.Azenhas,2013

Martin Aigner,A Course in Enumeration,Springer,2010

Keneth Bogart,Combinatorics Through Guided Discovery http://www.math.dartmouth.edu/news-resources/electronic/kpbogart

Miklós Bóna A Walk Through Combinatorics.An introduction to Enumeration and Graph Theory,World Scientific Publishing 2002

Peter J.Cameron Combinatorics: Topics,Techniques,Algorithms,Cambridge University Press,1994

Domingos M.Cardoso, Jerzy Szymanski,Mohammad Rostami,Matemática Discreta,Combinatória,Teoria grafos, Algoritmos,Escolar Editora, 2009

Reinhard Diestel Graph Theory,4th edition,Springer, 2010

George E. Martin,Counting The Art of Enumerative Combinatorics, Springer, 2001

J.M.Simões Pereira Matemática Discreta:Tóp.de Combinatória. Coimbra:Editora Luz da Vida 2006

J.M.Simões Pereira,Matemática Discreta:Grafos Redes e Aplicações,Editora Luz da Vida,2009

Richard Stanley,Enumerative Combinatorics, 1st volume,Cambridge Studies in Adavanced Mathematics49 Cambridge University Press,1997