Fac-simile prova d'esame, prima prova d'esame, seconda prova d'esame, terza prova d'esame, quarta prova d'esame.
Esercizi già consegnati:
- capitolo 1: 4, 6, 12, 35j, 38, 50a, 53a, 87.
- capitolo 2: 2, 14ab, 25a, 29a.
- capitolo 3: 44a, 45b, 46a, 58, 62ab, 70ab.
- capitolo 4: 19, 20, 33a.
Testo di riferimento principale:
R. Stanley, Enumerative Combinatorics, volume 1, second edition, Cambridge University Press, 2011.
Diario delle lezioni:
29/02/24: Contare insiemi e multinsiemi: coefficienti binomiali, composizioni, composizioni deboli, multinsiemi.
01/03/24: Coefficienti multinomiali. Riferimenti: sezione 1.2. Esercizi proposti: (capitolo 1) 2, 3, 8, 10, 25, 34. Permutazioni: rappresentazione standard e biezione fondamentale, tipo di una permutazione e permutazioni di tipo fissato.
07/03/24: Numero di permutazioni di [n] con un numero k di cicli (numeri di Stirling del primo tipo senza segno).
08/03/24: Tavola delle inversioni di una permutazione e distribuzione della statistica inv (numero di inversioni). Insieme delle discese di una permutazione, numero delle discese, numeri euleriani. Eccedenze ed eccedenze deboli di una permutazione, la biezione fondamentale trasforma le eccedenze deboli in non-discese. Riferimenti: sezioni 1.3 e 1.4. Esercizi proposti: (capitolo 1) 35, 36, 37, 49a, 50, 51, 52, 117, 120, 127.
14/03/24: Statistica maj (major index), biezione che trasforma maj in inv (inv e maj sono equidistribuite).
15/03/24: La biezione che trasforma maj in inv preserva l'insieme delle discese della permutazione inversa (reading set), segue che inv e maj hanno distribuzione simmetrica. Matrice di una permutazione e diagramma di una permutazione. Permutazioni di [n] che evitano una fissata permutazione di [3] e numeri di Catalan. Riferimenti: sezioni 1.4 e 1.5. Esercizi proposti: (capitolo 1) 57, 58, 60.
21/03/24: q-analoghi degli interi positivi, del fattoriale, dei coefficienti binomiali e multinomiali. Permutazioni di un multinsieme e distribuzione della statistica inv. Riferimenti: sezione 1.7. Esercizi proposti: (capitolo 1) 56, 62, 64, 176.
22/03/24: Partizioni: ricorsione per il numero di partizioni di n di lunghezza k. Funzioni generatrici che contano le partizioni con diagramma contenuto in un rettangolo fissato, le partizioni con al più k parti, le partizioni con k parti, tutte le partizioni, partizioni con restrizioni fissate sulle molteplicità. Riferimenti: sezioni 1.7 e 1.8. Esercizi proposti: (capitolo 1) 22, 70, 71, 73, 75, 80.
04/04/24: Tre identità con produttorie infinite interpretabili in termini di partizioni e loro varianti finite (q-analogo dello sviluppo della potenza del binomio). Riferimenti: sezione 1.8. Esercizi proposti: (capitolo 1) 76, 100. Dodici modi per contare le applicazioni tra due insiemi finiti. Numeri di Stirling del secondo tipo: ricorsione e serie generatrice.
05/04/24: Numeri di Bell: ricorsione e serie generatrice. 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. Riferimenti: sezione 1.9. Esercizi proposti: (capitolo 1) 45, 107.
11/04/24: Il principio di inclusione-esclusione. Applicazioni ed esempi: probleme des rencontres ovvero permutazioni che non fissano nessun elemento.
12/04/24: Numero di permutazioni con insieme delle discese fissato, e q-analogo. Permutazioni con restrizioni sul grafico (non-attacking rooks): probleme des menages. Riferimenti: sezioni 2.1, 2.2 e 2.3. Esercizi proposti: (capitolo 2) 3, 4, 5, 8, 9, 16, 20.
19/04/24: Insiemi parzialmente ordinati (poset): definizione, esempi fondamentali, terminologia (intervalli, catene, lunghezza). Poset graduati, rango e funzione generatrice di un poset graduato. Costruzioni astratte di poset: somma disgiunta, prodotto diretto, duale, poset dei morfismi tra due poset. Convoluzione e algebra di incidenza. Riferimenti: sezioni 3.1, 3.2 e 3.6. Esercizi proposti: (capitolo 3) 4, 6, 8. Inoltre, sempre per esercizio, dimostrare l'ultima affermazione della sezione 3.6.
02/05/24: Principio di inversione di Moebius. 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. Riferimenti: sezioni 3.7 e 3.8. Esercizi proposti: (capitolo 3) 84, 88, 122, 132, 136.
03/05/24: Poset delle facce (non vuote) di un complesso simpliciale, il complesso d'ordine del poset delle facce di un complesso simpliciale è la sua suddivisione baricentrica. Il valore che la funzione di Moebius assume su un intervallo corrisponde alla caratteristica di Eulero (ridotta) del link di un simplesso. Riferimenti: sezione 3.8. Reticoli, reticoli semimodulari e modulari: definizione, prime proprietà ed esempi. Riferimenti: sezione 3.3. Esercizio proposto: (capitolo 3) 25. Inoltre, sempre per esercizio, dimostrare che ogni sottoreticolo di un reticolo modulare finito è modulare.
10/05/24: Complementi, atomi e coatomi, reticoli geometrici: esempi. Reticoli distributivi finiti: modularità, esempi. Reticolo degli ideali d'ordine di un poset finito e Teorema di Birkhoff. Riferimenti: sezioni 3.3 e 3.4. Esercizi proposti: (capitolo 3) 12, 30, 36, 38, 50, 61.
16/05/24: 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 è a segni alterni. Calcolo della funzione di Moebius del reticolo dei sottospazi di (F_q)^n e del reticolo delle partizioni di un insieme. Riferimenti: sezioni 3.9 e 3.10. Esercizi proposti: (capitolo 3) 86, 119, 123, 133.
17/05/24: Poset binomiali: funzione fattoriale di un poset binomiale, algebra di incidenza ridotta e isomorfismo con l'algebra delle serie di potenze formali, esempi. Riferimenti: sezione 3.18. Esercizio proposto: (capitolo 3) 199.
23/05/24: Funzioni generatrici razionali: teorema di caratterizzazione delle successioni che danno luogo a funzioni generatrici razionali, esempi, relazione di reciprocità. Riferimenti: sezioni 4.1 e 4.2. Esercizi proposti: (capitolo 4) 11, 44.
24/05/24: Il caso particolare dei polinomi e dei quasipolinomi. Riferimenti: sezioni 4.3 e 4.4. Esercizi proposti: (capitolo 4) 15, 16. Introduzione ai sistemi di equazioni lineari omogonee diofantee. Riferimenti: sezione 4.5.
30/05/24: Generalità sui coni convessi poliedrali, triangolazioni di coni convessi poliedrali, funzione di Moebius del poset delle facce di una triangolazione di un cono convesso poliedrale puntato, applicazione alla funzione generatrice dell'insieme delle soluzioni di un sistema di equazioni lineari omogenee diofantee. Riferimenti: sezione 4.5.
31/05/24: Monoidi simpliciali, quasi-generatori e funzione generatrice di un monoide simpliciale. La funzione generatrice dell'insieme delle soluzioni di un sistema di equazioni lineari omogenee diofantee è razionale, descrizione del denominatore in termini di elementi completamente fondamentali. Teorema di reciprocità. Funzione generatrice della cardinalità degli insiemi di livello. Riferimenti: sezione 4.5. Esercizi proposti: 30, 31, 32, 43.
06/06/24: Quasipolinomio di Ehrhart di un politopo convesso razionale, descrizione del denominatore della sua funzione generatrice razionale, relazione di reciprocità, caso dei politopi convessi interi. Riferimenti: sezione 4.6. Esercizi proposti: 36, 60, 61.