Fac-simile prova scritta, primo appello, secondo appello, terzo appello, quarto appello, , quinto appello.
Testo di riferimento principale:
R. Stanley, Enumerative Combinatorics, volume 1, second edition, Cambridge University Press, 2011.
Diario delle lezioni:
02/03/23: Contare insiemi e multinsiemi: coefficienti binomiali, composizioni, composizioni deboli, multinsiemi, coefficienti multinomiali. Esercizi proposti: (capitolo 1) 2, 3, 8, 10, 24, 25, 34.
03/03/23: Permutazioni: rappresentazione standard e biezione fondamentale, tipo di una permutazione e permutazioni di tipo fissato, valore atteso del numero di k-cicli di una permutazione random.
09/03/23: Numero di permutazioni di [n] con un numero k di cicli (numeri di Stirling del primo tipo senza segno). Tavola delle inversioni di una permutazione e distribuzione della statistica inv (numero di inversioni). Esercizi proposti: (capitolo 1) 35, 36, 37, 117, 120, 127.
10/03/23: Cenni ai q-analoghi degli interi positivi, del fattoriale e dei coefficienti binomiali. Insieme delle discese di una permutazione, numero delle discese, numeri euleriani. Eccedenze ed eccedenze deboli di una permutazione, la biezione fondamentale trasforma le non discese in eccedenze deboli.
16/03/23: Statistica maj (major index), biezione che trasforma maj in inv (inv e maj sono equidistribuite). La stessa biezione preserva l'insieme delle discese della permutazione inversa (reading set), segue che inv e maj hanno distribuzione simmetrica. Esercizi proposti: (capitolo 1) 49a, 50, 51, 52.
17/03/23: Matrice di una permutazione e diagramma di una permutazione. Permutazioni di [n] che evitano una fissata permutazione di [3] e numeri di Catalan. Biezione tra permutazioni di [n] e alberi binari crescenti su n vertici.
23/03/23: Biezione tra permutazioni di [n] e alberi non ordinati crescenti su n+1 vertici. Funzione generatrice dei numeri di Eulero. Biezione tra permutazioni di [n] e alberi min-max, definizione dei polinomi ab-indice (statistica dell'insieme delle discese) e cd-indice (tramite le classi d'equivalenza min-max), il primo si ottiene dal secondo ponendo c=a+b e d=ab+ba. Esercizi proposti: (capitolo 1) 57, 58, 60, 61, 63, 134, 135, 139.
24/03/23: Il numero delle permutazioni di [n] con insieme delle discese fissato è sempre minore o uguale al numero di Eulero E_n, e vale l'ugualianza solo per le permutazioni alternanti e per le permutazioni alternanti a rovescio. Numeri di Motzkin. Definizione di permutazione di un multinsieme e q-analogo dei coefficienti multinomiali. Distribuzione della statistica inv per le permutazioni di multinsiemi. Esercizi proposti: (capitolo 1) 148.
30/03/23: Partizioni: ricorsione per il numero di partizioni di n di lunghezza k. Numero di partizioni con diagramma contenuto in un rettangolo fissato: funzione generatrice e corrispondenza con le permutazioni di un multinsieme su due elementi. Esercizi proposti: (capitolo 1) 56, 62, 64, 176.
31/03/23: Funzioni generatrici che contano le partizioni con al più k parti, le partizioni con k parti, tutte le partizioni. Esercizi: partizioni autoconiugate, partizioni con parti distinte, partizioni con parti dispari. Tre identità con produttorie infinite interpretabili in termini di partizioni e loro varianti finite (q-analogo dello sviluppo della potenza del binomio). Esercizi proposti: (capitolo 1) 22, 70, 71, 73, 75, 76, 80, 89, 100, 103.
13/04/23: Dodici modi per contare le applicazioni tra due insiemi finiti. Numeri di Stirling del secondo tipo e numeri di Bell: ricorsione e serie generatrici. I numeri di Stirling del secondo tipo sono i coefficienti della matrice di cambiamento di coordinate (matrice di transizione) dalla base di K[x] data dai monomi x^n alla base data dai polinomi [x]_n, i numeri di Stirling del primo tipo segnati sono i coefficienti della matrice inversa. Formalismo del calcolo alle differenze finite. Esercizi proposti: (capitolo 1) 45, 107.
14/04/23: Il principio di inclusione-esclusione. Applicazioni ed esempi: probleme des rencontres ovvero permutazioni che non fissano nessun elemento. Esercizi proposti: (capitolo 2) 3, 4, 5, 8, 9.
20/04/23: Numero di permutazioni con insieme delle discese fissato, e q-analogo. Permutazioni con restrizioni sul grafico (non-attacking rooks): enunciato.
21/04/23: Permutazioni con restrizioni sul grafico: dimostrazione. Probleme des menages. Esercizi proposti: (capitolo 2) 16, 19, 20, 22. Insiemi parzialmente ordinati (poset): definizione, esempi fondamentali, terminologia (intervalli, catene, lunghezza). Poset graduati, rango e funzione generatrice di un poset graduato.
27/04/23: Costruzioni astratte di poset: somma disgiunta, prodotto diretto, duale, poset dei morfismi tra due poset. Convoluzione e algebra di incidenza. Principio di inversione di Moebius. Esercizi proposti: (capitolo 3) 4, 6, 8, 76, 84, 88.
28/04/23: Calcolo della funzione di Moebius negli esempi più semplici. Teorema di Hall e interpretazione in termini di caratteristica di Eulero del complesso simpliciale d'ordine. Reticoli: definizione e prime proprietà. Esercizi proposti: (capitolo 3) 132, 136.
04/05/23: Reticoli semimodulari e modulari, complementi, atomi e coatomi, reticoli geometrici: esempi. Matroidi: definizione, matroidi rappresentabili, circuiti e matroidi grafiche, esempi. Esercizio proposto: 1.1.2 (J. Oxley, Matroid Theory, Oxford University Press, 1992).
05/05/23: Matroidi: basi, restrizione, rango, chiusura, sottospazi, iperpiani. Il poset dei sottospazi di una matroide è un reticolo geometrico. Le matroidi semplici supportate su un insieme E sono in corrispondenza biunivoca con i reticoli geometrici aventi E come insieme degli atomi. L'algoritmo greedy. Esercizi proposti: (Oxley) 1.2.5, 1.3.2; (Stanley, capitolo 3) 36, 37.
11/05/23: Reticoli distributivi finiti: modularità, esempi. Reticolo degli ideali d'ordine di un poset finito e Teorema di Birkhoff. Generalizzazzione ai reticoli distributivi finitari (senza dimostrazione), reticolo di Young. Esercizi proposti: (capitolo 3) 12, 22, 30, 38, 41, 50, 61, 72.
12/05/23: Algebra di Moebius, Teorema di Weisner, Teorema cross-cut, descrizione della funzione di Moebius di un reticolo distributivo finito. Applicazione del teorema di Weisner al caso dei reticoli semimodulari finiti, la funzione di Moebius di un reticolo semimodulare finito è alternante. Calcolo della funzione di Moebius del reticolo dei sottospazi di (F_q)^n e del reticolo delle partizioni di un insieme. Esercizi proposti: (capitolo 3) 86, 100, 119, 122, 123, 133.
18/05/23: Polinomio caratteristico di un poset graduato finito con minimo. Arrangiamenti di iperpiani: dimensione, rango, poset di incidenza, arrangiamenti centrali, polinomio caratteristico, deletion-restriction.
19/05/23: Arrangiamenti reali: numero delle regioni e numero delle regioni relativamente limitate. Arrangiamenti razionali: metodo dei campi finiti. Esercizi proposti: (capitolo 3) 108, 110, 113, 116.
25/05/23: Il polinomio zeta di un poset finito, sottoposet di rango selezionato, poset euleriani (teorema di dualità). Esercizi proposti: (capitolo 3) 138, 140, 147, 149, 150, 156, 157, 174, 175, 184.
26/05/23: Poset binomiali: funzione fattoriale di un poset binomiale, algebra di incidenza ridotta e isomorfismo con l'algebra delle serie di potenze formali, esempi.