Discrete mathematics in computer science. Introduction to the combinatorics of maps, set partitions, integer partitions and permutations. Principle of inclusion-exclusion and applications. Generating functions and applications to the enumeration of combinatorial structures.
Posets and lattices; formal concept analysis; distributive lattices and Boolean algebras; Galois connections; CPO and fixed point theorems.
Incidence algebras; Moebius inversion and applications.
M. Cerasoli, F. Eugeni, M. Protasi, Elementi di Matematica Discreta, Zanichelli.
B. A. Davey, H. A. Priestley, Introduction to lattices and order, Cambridge University Press.
E. Munarini, N. Zagaglia Salvi, Matematica Discreta, Citta’ Studi Edizioni.
R. P. Stanley, Enumerative Combinatorics, vol. I e II, Cambridge University Press.
Learning Objectives
The course aims at providing the basic notions of enumerative and algebraic combinatorics and the theory of posets and lattices, also focussing on the applications to theoretical computer science.
Prerequisites
Basic notions of computer science and linear algebra.
Teaching Methods
Lectures.
Further information
Attendance of lectures, practice and lab: Recommended
Office hours: by appointment
Contact:
Dipartimento di Matematica e Informatica "Ulisse Dini"
Viale Morgagni, 65
50134 FIRENZE
Tel: 055 2751484
Fax: 055 4237436
E-mail: luca.ferrari@unifi.it
During the course some homeworks will be assigned. These homework are mandatory in order to make the final oral exam.
Type of Assessment
Exercises at home, brief seminar talk (about 10 minutes) on a topic related with the course but not included in the program, oral exam (one question on the combinatorics part, one question on the psoet and lattices part).
Course program
Discrete mathematics in computer science. Introduction to enumerative combinatorics: maps, injective and surjective maps and special numbers associated with their enumeration; the twelvefold way; basic enumerative combinatorics of set partitions, integer partitions and permutations. The principle of inclusion-exclusion and some applications: the derangement problem, the enumeration of surjective maps, the Euler Phi function, the ménages problem. Generating functions: basic notions, elementary manipulations of generating functions, rational and algebraic generating functions, applications to the enumeration of combinatorial structures.
Posets and lattices: basic notions and main applications in computer science; formal concept analysis; distributive lattices and Boolean algebras, applications to circuits, representation theorems in the finite case; closure operators and Galois connections; complete posets and fixed point theorems.
Incidence algebras and Moebius functions; Moebius inversion theorem; some applications (enumeration of necklaces, chromatic polynomial of a graph).