Discrete Mathematics

Code:

M3011

Acronym:

M3011

Level:

300

Keywords
Classification	Keyword
OFICIAL	Mathematics

Instance: 2016/2017 - 2S

Active?	Yes
Responsible unit:	Department of Mathematics
Course/CS Responsible:	Bachelor in Biology

Cycles of Study/Courses

Acronym	No. of Students	Study Plan	Curricular Years	Credits UCN	Credits ECTS	Contact hours	Total Time
L:B	0	Official Study Plan	3	-	6	56	162
L:M	39	Official Study Plan	2	-	6	56	162
			3
L:Q	0	study plan from 2016/17	3	-	6	56	162

Teaching language

Suitable for English-speaking students

Objectives

With this course, it is intended that students will know and understand some of the main results of Combinatorics that, for its present relevance within Mathematics, and by its special applicability, inside and outside Mathematics, should be of general knowledge for mathematicians. In this course the students should also develop their ability to solve combinatorial problems and the ability do solve problemas looking for the more suitable structure.

Learning outcomes and competences

Upon completing this course, the student should know and be able to apply the concepts and results covered in the course. It is intended that this unit contribute to the furthering of skills in the field of discrete mathematics. In summary, it is intended that upon completion of this class the student can:

-Understand and apply fundamental combinatorial techniques as well as understand when these can or cannot be applied.
-Use appropriate techniques and problem solving skills on new problems.
-Recognize mathematical structures (e.g. algebraic ones) in combinatorial problems, can formulate them and solve them using the corresponding techniques.
-Be mathematically creative and inquisitive, being capable of formulating interesting new questions in combinatorics.

Working method

Presencial

Pre-requirements (prior knowledge) and co-requirements (common knowledge)

Familiarity with basic concepts and techiques from linear algebra (vector spaces, matrices, determinants, characteristic polynomial, eigenvalues) and with the basic concepts of group theory.

Program

The following forms a merely indicative list of topics for the syllabus; the syllabus may vary slightly from year to year. 
1. Generating functions and operations on combinatorial structures.
2. Solving enumeration problems using generating functions: multinomial coefficients, Catalan numbers, partitions, Stirling numbers, Motzkin numbers, tilings, etc.
3. Walks in graphs, random walks.
4. Posets, boolean algebras, group actions on boolean algebras and their corresponding quotient posets.
5. Sperner property, unimodality, simetry. Edge reconstruction conjecture.
6. Mobius inversion.
7. Young diagrams and tableaux, RSK correspondence.
8. Polya's theory of enumeration under group action.
9. Matrix-tree theorem.

Mandatory literature

Stanley Richard P.; Enumerative combinatorics. ISBN: 0-534-06546-5
Brualdi Richard A.; Introductory combinatorics. ISBN: 0-13-181488-5
Lint J. H. Van; A course in combinatorics. ISBN: 0-521-42260-4
Stanley Richard P.; Algebraic combinatorics. ISBN: 9781461469971

Complementary Bibliography

Bondy J. A.; Graph theory with applications. ISBN: 0-333-17791-6
Mazur David R.; Combinatorics. ISBN: 9780883857625

Teaching methods and learning activities

Expositional classes with discussion of examples and resolution of exercises.

Evaluation Type

Distributed evaluation with final exam

Assessment Components

designation	Weight (%)
Exame	80,00
Participação presencial	10,00
Trabalho escrito	10,00
Total:	100,00

Calculation formula of final grade

The final grade is the weighted average of the in-class grade and the final exam grade, along the following guidelines:

a) In-class grade: 4 out of 20 (20%)

During class students will be encouraged to, individually or in groups, solve problems and present them orally in class, and also to typeset the notes for one class in LaTeX. Each problem presented orally will be worth 1 out of 20 and a set of class notes typeset in LaTeX by one student will be worth 4 out of 20. As an alternative to the latter option, a group of two or three students may submit the typeset notes of two classes, also affording a maximum mark of 4 out of 20. These marks will be added and the student's grade for this part will be the minimum between the corresponding sum and 4 out of 20.

b) Final exam: 16 out of 20 (80%)

In order to obtain a final grade greater than 16 out of 20, a student may be submitted to an additional assignment.

Students with a final grade of at least 8,5 but lower than 9,5 may be submitted to an additional assessment in order to determine their aproval or failure, but if at all, this can only occur during the second exam period (época de recurso).

Any student may be required to take an oral examination should there be any doubts concerning his/her performance on certain assessment pieces.

Special assessment (TE, DA, ...)

Special exams will consist of a written test, which might be preceded by an eliminatory oral test to assess whether the student satisfies minimum requirements to tentatively pass the written test.

Classification improvement

The distributed part of the assessment (all except for the final exam) cannot be retaken.

Observations

Artigo 13º do Regulamento Geral para Avaliação dos Discentes de Primeiros Ciclos, de Ciclos de Estudos Integrados de Mestrado e de Segundos Ciclos da U.Porto, aprovado em 19 de Maio de 2010 (cf. http://www.fc.up.pt/fcup/documentos/documentos.php?ap=3&ano=2011): "A fraude cometida na realização de uma prova, em qualquer das suas modalidades, implica a anulação da mesma e a comunicação ao órgão estatutariamente competente para eventual processo disciplinar."

Any student may be required to take an oral examination should there be any doubts concerning his/her performance on certain assessment pieces.

Jury:
António Guedes de Oliveira 
Samuel António de Sousa Dias Lopes