Discrete mathematics in computer science. Introduction to the combinatorics of maps, set partitions, integer partitions and permutations. Principle of inclusion-exclusion and applications. Rational and algebraic generating functions.
Posets and lattices; formal concept analysis; distributive lattices and Boolean algebras; Galois connections; CPO and fixed point theorems; algebraic lattices.
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. At the end of the course the students will acquire a solid knowledge on some aspects of enumerative combinatorics and poset andd lattice theory and will be able to solve medium level problems in such fields. The course also gives the necessary background to pursue further studies in discrete mathematics.
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
E-mail: luca.ferrari@unifi.it
During the course some homeworks will be assigned. These homeworks are mandatory in order to make the final oral exam.
Type of Assessment
Homeworks, 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 poset 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.
Posets and lattices: basic notions and main applications in computer science; formal concept analysis; distributive lattices and Boolean algebras; Stone and Birkhoff representation theorems; closure operators and Galois connections; complete posets and fixed point theorems; algebraic closure systems, algebraic closure operators and algebraic lattices.
Incidence algebras and Moebius functions; Moebius inversion theorem; techniques for computing the Moebius function; some applications (enumeration of necklaces, chromatic polynomial of a graph, enumeration of connected graphs).
Generating functions: basic notions and examples; formal power series algebra; rational generating functions and related combinatorial objects (lattice paths, polyominoes, trees, permutations); algebraic generating functions and related combinatorial objects (lattice paths, polyominoes, trees, permutations); Catalan numbers.