85168 - DISCRETE MATHEMATICS

Scheda insegnamento

Anno Accademico 2018/2019

Conoscenze e abilità da conseguire

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.

Programma/Contenuti

Elementi di Combinatoria Enumerativa con applicazioni alla Probabilita' Discreta.

FUNZIONI TRA INSIEMI FINITI. Modello dell'occupazione. Modello delle parole. Il numero di funzioni tra insiemi finiti.
Alcuni principi generali. Funzioni iniettive. Parole crescenti. Funzioni crescenti.

MULTIINSIEMI. Il problema delle file. Fattoriale crescente. Multiinsiemi. Coefficienti multiinsiemistici. Parole non decrescenti.
Funzioni non decrescenti.

EQUAZIONI A SOLUZIONI INTERE NON NEGATIVE. Statistiche di Bose-Einstein e Fermi-Dirac. Problema di Gergonne generalizzato.

COEFFICIENTI MULTINOMIALI E COMPOSIZIONI DI UN INSIEME FINITO.

PARTIZIONI. Relazioni di equivalenza e partizioni. Numeri di Stirling di II specie.

Numeri di Bell. Coefficienti di Faa' di Bruno.

PERMUTAZIONI. Grafi orientati. Grafi di permutazione. Cicli. Fattorizzazione in cicli di una permutazione. Coefficienti di Cauchy.
Numeri di Stirling di I specie.

METODI DEL CRIVELLO. Principio di inversione di Moebius (caso insiemistico). Principio di inclusione/esclusione: formule di Sylvester
e di C.Jordan. Applicazioni: funzione di Eulero, numero delle funzioni suriettive, problema dei"menages".

Testi/Bibliografia

Note del Docente su Files Pdf scaricabili dal sito

Metodi didattici

Verranno discussi i concetti e metodi generali tipici
della Combinatoria Enumerativa con
applicazioni alla Probabilita' discreta

Durante le lezioni verranno proposti esercizi, alcuni dei quali svolti dal Docente, altri verranno lasciati come lavoro individuale.

Le esercitazioni hanno lo scopo di fornire la possibilitá a ciascun studente di misurarsi nella elaborazione di
soluzioni autonome dei problemi concreti che verranno posti applicando le nozioni teoriche apprese durante le lezioni.

Modalità di verifica dell'apprendimento

L'esame consiste di una prova finale orale della durata di 45 minuti. Si verifichera' la competenza dello studente sia a livello di acquisizione di metodi e concetti che di applicazione a casi concreti.

Lo Studente preparerà cinque dimostrazioni a propria scelta (fra quelle discusse durante lo svolgimento del corso). Una tra esse sarà oggetto di domanda di esame.

Orario di ricevimento

Consulta il sito web di Andrea Brini