Discrete Mathematics

Recommended Prerequisites

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.

Teaching Methods

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.

Learning Outcomes

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.

Work Placement(s)

No

Syllabus

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).

Head Lecturer(s)

João Eduardo da Silveira Gouveia

Assessment Methods

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

Bibliography

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