85168 - Discrete Mathematics

Learning outcomes

By the end of the course the student is familiar with the basic concepts and results of enumerative combinatorics and of their links with discrete probability. Following the so-called Rota's way, the student learns the main enumerative statistics for subsets, multiset, compositions, partitions, permutations and graphs, the sieve methods and Moebius inversion techniques.

Course contents

Elements of Enumerative Combinatorics with Applications to Discrete Probability

This course provides an introduction to enumerative combinatorics and graph theory, with a focus on techniques and structures relevant to statistical theory and applications. Special emphasis will be placed on asymptotic enumeration and probabilistic interpretations of combinatorial objects, which are particularly useful in statistical modeling, experimental design, and computational statistics. The course balances theoretical foundations with practical problem-solving, preparing students to apply combinatorial methods in advanced statistical research.



FUNCTIONS BETWEEN FINITE SETS. Occupancy model. Word model. The number of functions between finite sets.
Some general principles. Injective functions. Increasing words. Increasing functions.

MULTISETS. The queue problem. Rising factorial. Multisets. Multiset coefficients. Non-decreasing words.
Non-decreasing functions.

EQUATIONS WITH NON-NEGATIVE INTEGER SOLUTIONS. Bose-Einstein and Fermi-Dirac statistics. Generalized Gergonne problem.

MULTINOMIAL COEFFICIENTS AND COMPOSITIONS OF A FINITE SET.

PARTITIONS. Equivalence relations and partitions. Stirling numbers of the second kind. Bell numbers. Faa di Bruno's coefficients.

PERMUTATIONS. Directed graphs. Permutation graphs. Cycles. Cycle factorization of a permutation. Cauchy coefficients.
Stirling numbers of the first kind.

SIEVE METHODS. Moebius inversion principle (set-theoretic case). Inclusion-exclusion principle: formulas of Sylvester and C. Jordan.
Applications: Euler's totient function, number of surjective functions, the "ménages" problem. Applications in statistical dependence and event probabilities

Catalan numbers and their combinatorial interpretations

Bijective proofs. Double counting techniques.Applications in random sampling and resampling methods

Directed and undirected graphs. Isomorphism of graphs. Paths and cycles in graphs. Connected graphs, cut-sets.

Graph Coloring and Partitioning. Chromatic number and chromatic polynomial. Coloring algorithms and their applications in statistics

Trees and Forests. Spanning trees. Minimum spanning tree (Kruskal's and Prim's algorithms). Applications to hierarchical clustering and phylogenetic trees


Graph Algorithms:
Shortest Path Algorithms.Dijkstra's and Bellman-Ford algorithms. Applications in optimization and network flow.

Max Flow/Min Cut Theorems. Ford-Fulkerson algorithm. Applications in flow networks and statistical inference

Readings/Bibliography

notes of the course

Teaching methods

lectures, exercises

Assessment methods

written and oral exam

Teaching tools

virtuale webpage of the course

Office hours

See the website of Luca Moci

See the website of Alessandro D'Andrea