Module page
Discrete Mathematics
| academic year: | 2013/2014 |
| instructor: | Claudia Malvenuto |
| degree course: | Mathematics for applications (magistrale), I year |
| type of training activity: | caratterizzante |
| credits: | 6 (48 class hours) |
| scientific sector: | MAT/02 Algebra |
| teaching language: | italiano |
| period: | II sem (06/03/2014 - 13/06/2014) |
Lecture meeting time and location
Presence: highly recommended
Module aims: The aim of the course is to present some general principles and some fundamental methods of Discrete Mathematics (such as inclusion-exclusion principle, the method of recurrence relations). They will be used in in the resolution of problems of various areas, such as enumerative combinatorics, poset theory, graph theory.
Module subject:
Programme of the course: Partial orders. Basic rules for counting.
Bijective proofs. Pigeonhole principle.
Combinatorial structures and fundamental sequences of integers.
Factorial, binomial coefficient and its combinatorial interpretation. Binomial theorem.
Multinomial coefficient. Increasing factorial.
Permutations. The symmetric group. Inversions and descents of a permutation.
Recursive relations. Stirling numbers of I and II kind.
Fibonacci numbers.
Genarating functions. The algebra of formal series.
Bell numbers
Lattices and inclusion exclusion principle
Applications: Euler function and number of surjective functions.
Suggested reading:
- J. H. van Lint and R.M. Wilson, A course on Combinatorics. Cambridge University Press, (2001).
- P.J. Cameron: Combinatorics: Topics, Techiques, Algorithms, Cambridge University Press, (1991)
- J.Matousek, J.Nesetril: Invitation to Discrete Mathematics. Clarendon Press (1998).
Type of course: standard
Useful link: http://www1.mat.uniroma1.it/people/malvenuto/MatDiscreta/index.html
Knowledge and understanding: Gli studenti conosceranno le principali tecniche usate in Matematica Discreta (regole di conteggio, principio di inclusione-esclusione, relazioni ricorsive, serie formali). Avranno inoltre una conoscenza dei reticoli fondamentali in Combinatoria e delle loro proprietà e più in generale conosceranno la teoria dei reticoli nella quale saranno in grado di inquadrare il principio di inclusione -eslusione.
Skills and attributes: Gli studenti saranno in grado di risolvere semplici problemi di Combinatoria enumerativa. sapranno inoltre risolvere relazioni ricorsive lineari omogene anche usando le funzioni generatrici. Le competenze acquisite permetteranno di affrontare problemi riguardanti le principali strutture discrete.
Personal study: the percentage of personal study required by this course is the 65% of the total.