85168 - Discrete Mathematics

Course Unit Page

  • Teacher Andrea Brini

  • Credits 6

  • SSD MAT/02

  • Language English

  • Campus of Bologna

  • Degree Programme Second cycle degree programme (LM) in Statistical Sciences (cod. 9222)

Academic Year 2021/2022

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 II species. Bell numbers. Faa 'Bruno coefficients.

PERMUTATIONS. Oriented graphs. Permutation Graphs. Cycles. Factoring in cycles of a permutation. Coefficients of Cauchy.
Stirling Numbers of I Species.

SIEVE METHODS. Moebius Inversion Principle (set-theoretic case). Principle of inclusion / exclusion: Sylvester and Ch. Jordan formulas.

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

Readings/Bibliography

Teacher's Notes on Pdf Files downloadable from the site

Teaching methods

General concepts and general methods of Enumerative Combinatorics will be discussed,
with Applications to Discrete Probability.

During the lessons will be proposed exercises, some of which are carried out by the Teacher, others will be left as individual work.

The exercises aim to provide each student with the ability in the processing autonomous solutions to the concrete problemsby applying the theoretical notions learned during the course.

Assessment methods

The examination consists of an oral examination lasting 45 minutes. Will occur 'the student's competency both in terms of acquisition of concepts and methods, with application to concrete cases.

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

Office hours

See the website of Andrea Brini