| Code |
13905
|
| Year |
1
|
| Semester |
S2
|
| ECTS Credits |
6
|
| Workload |
TP(60H)
|
| Scientific area |
Mathematics
|
|
Entry requirements |
N.A.
|
|
Learning outcomes |
- Apprehend some concepts and fundamental results of the partially ordered sets, enumeration theory and graph theory
- Analyse and understand proofs;
- Communicate, written and orally, using mathematical language;
- To recognize some examples of the application of the contents presented in the context of the exact and social sciences.
|
|
Syllabus |
1- Partially ordered sets and lattices.
Hasse diagram, Tarski's fixed point, distributive lattice, Boolean algebra.
2- Fundamental principles.
Fundamental counting principle, pigeonhole and double counting. Permutations and combinations.
3- Subsets and binomial coefficients.
Properties of binomial coefficients, binomial theorem.
4- Generating functions and recurrence relations.
Generating functions, operations on generating functions, binomial theorem. Fibonacci numbers, linear and non-linear recurrences.
5- Partitions and permutations.
Partitions: Bell and Stirling numbers. Permutations: cycle decomposition and Stirling numbers.
6- The Principle of inclusion-exclusion.
Surjections and Stirling numbers, derangements.
7- Graph theory.
Graph isomorphism, incidence and adjacency matrices, paths and circuits, Eulerian graphs, Fleury algorithm, Hamiltonian graphs, graphs coloring, trees, minimal tree problem, shorter path problem, oriented graphs, maximum flow problem.
|
|
Main Bibliography |
1- Peter J. Cameron, Notes on Combinatorics, 2013.
2- Peter J. Cameron, Combinatorics: Topics, Techniques, Algorithms (2nd edition), Cambridge University Press, 1996.
3- Brian A. Davey, Hilary A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 2002.
4- Norman Biggs, Discrete Mathematics (2nd edition), Oxford University Press, 2002.
5- Bela Bollobas, Modern Graph Theory, Springer-Verlag, 2002.
6- Domingos M. Cardoso, J. Szymanski, Mohammad Rostami, Matemática Discreta Combinatória, Teoria dos Grafos e Algoritmos, Escolar Editora, 2008
|
|
Language |
Portuguese. Tutorial support is available in English.
|