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

Introduction to elementary Enumerative Combinatorics with applications to Discrete Probability.

FUNCTIONS BETWEEN FINITE SETS. The occupancy model. The word model. The number of functions between finite sets.
Some general principles. Injective functions. Increasing words. Increasing functions. Decreasing factorial.

MULTISETS. The queues problem. Increasing factorials. Multisets. Multi-Sequential Coefficients. Non-deceasing words.
Non-decreasing functions.

EQUATIONS WITH NON-NEGATIVE INTEGER SOLUTIONS. Statistics of Bose-Einstein, Fermi-Dirac and G. Gentile. The Generalized Gergonne problem .

MULTINOMIAL COEFFICIENTS AND COMPOSITIONS OF A FINITE SET.

PARTITIONS. Equivalence and partition relationships. Stirling numbers of the second kind. Bell numbers. Faa di 'Bruno coefficients.

PERMUTATIONS. Oriented graphs. Permutation Graphs. Cycles. Factoring in cycles of a permutation. Cauchy coefficients. Stirling Numbers of the first kind.

SIEVE METHODS. Moebius Inversion Principle (set-theoretic case). Inclusion/exclusion Principle: Sylvester and C.Jordan formulas.

Applications: The Euler phi function, counting surjective functions, problem of "menages".

Readings/Bibliography

Andrea Brini's lecture notes in Pdf file, available on the website

Teaching methods

We will discuss general concepts and general methods of Enumerative Combinatorics with Applications to Discrete Probability.

During the lessons we will discuss exercises, some of which will be solved by the lecturer, while others will be left as individual work.

The exercises aim to provide each student with the ability to build solutions to concrete problems, by applying the theoretical notions learned during the course.

Assessment methods

The examination will consists of an oral examination of 45 minutes. We will assess the student's learning both in terms of acquisition of theoretical concepts and methods, and the application to concrete examples.

The student will carefully study five proofs of his own choice
(among those discussed in the couse). One of them will be
discussed during the exam.

Office hours

See the website of Nicola Tito Pagani