Testi di riferimento:
R. Stanley, Enumerative Combinatorics, volume 1, second edition, Cambridge University Press, 2012.
R. Stanley, Enumerative Combinatorics, volume 2, second edition, Cambridge University Press, 2024.
Quinta prova scritta: venerdì 23 gennaio 2026 orario e aula da definire.
Diario delle lezioni:
06/03/25: Contare insiemi e multinsiemi: coefficienti binomiali, composizioni, composizioni deboli, multinsiemi.
07/03/25: 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.
13/03/25: Numero di permutazioni di [n] con un numero k di cicli (numeri di Stirling del primo tipo senza segno).
14/03/25: 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. Riferimenti: sezioni 1.3 e 1.4. Esercizi proposti: (capitolo 1) 35, 36, 37, 49a, 50, 51, 52, 117, 120, 127. q-analoghi degli interi positivi, del fattoriale e dei coefficienti binomiali.
20/03/25: Statistica maj (major index), biezione che trasforma maj in inv (inv e maj sono equidistribuite). 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. Riferimenti: sezione 1.4.
21/03/25: Matrice di una permutazione e diagramma di una permutazione. Permutazioni di [n] che evitano una fissata permutazione di [3] e numeri di Catalan. Riferimenti: sezione 1.5. Esercizi proposti: (capitolo 1) 57, 58, 60. Permutazioni di un multinsieme e distribuzione della statistica inv. Riferimenti: sezione 1.7. Esercizi proposti: (capitolo 1) 56, 62, 64, 176.
27/03/25: 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.
01/04/25: 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.
03/04/25: Numeri di Stirling del secondo tipo: ricorsione e serie generatrice. 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.
04/04/25: Il principio di inclusione-esclusione. Applicazioni ed esempi: probleme des rencontres ovvero permutazioni che non fissano nessun elemento. Numero di permutazioni con insieme delle discese fissato.
08/04/25: q-analogo del numero di permutazioni con insieme delle discese fissato. 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.
10/04/25: 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. Riferimenti: sezioni 3.1 e 3.2. Esercizi proposti: (capitolo 3) 4, 6, 8.
11/04/25: Convoluzione e algebra di incidenza. Principio di inversione di Moebius. Calcolo della funzione di Moebius negli esempi più semplici. Riferimenti: sezioni 3.6, 3.7 e 3.8. Esercizi proposti: (capitolo 3) 84, 88, 122.
06/05/25: Teorema di Hall e interpretazione in termini di caratteristica di Eulero del complesso simpliciale d'ordine. Riferimenti: sezione 3.8. Esercizi proposti: (capitolo 3) 132 e 136. Reticoli, reticoli semimodulari e modulari: definizione, prime proprietà ed esempi. Riferimenti: sezione 3.3. Esercizio proposto: (capitolo 3) 25.
08/05/25: 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.
09/05/25: 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.
15/05/25: Poset binomiali: funzione fattoriale di un poset binomiale, algebra di incidenza ridotta e isomorfismo con l'algebra delle serie di potenze formali, esempi. Formule di prodotto e composizione di funzioni generatrici esponenziali. Riferimenti: sezione 3.18 e sezione 5.1 (secondo volume). Esercizi proposti: (capitolo 3) 199 e (capitolo 5) 1.
16/05/25: Funzioni generatrici razionali: teorema di caratterizzazione delle successioni che danno luogo a funzioni generatrici razionali, esempi. Riferimenti: sezioni 4.1 e 4.2. Esercizi proposti: (capitolo 4) 11, 44.
22/05/25: Relazione di reciprocità per funzioni generatrici razionali. Polinomi e quasipolinomi. Riferimenti: sezioni 4.3 e 4.4. Esercizi proposti: (capitolo 4) 15, 16.
23/05/25: Algebra delle funzioni simmetriche: funzioni simmetriche monomiali, funzioni simmetriche elementari, funzioni simmetriche omogenee complete. Riferimenti: sezioni 7.1--7.5. Esercizi proposti: (capitolo 7) 2, 3, 4.
29/05/25: L'involuzione che scambia funzioni simmetriche elementari e funzioni simmetriche omogenee complete. Funzioni simmetriche di Newton (somme di potenze). Il prodotto scalare rispetto al quale le funzioni simmetriche monomiali e le funzioni simmetriche omogenee complete sono basi duali: le funzioni simmetriche di Newton sono una base ortogonale, l'involuzione è un'isometria. Riferimenti: sezioni 7.6, 7.7 e 7.9. Esercizi proposti: (capitolo 7) 5, 6, 9.
30/05/25: Tableaux semi-standard (sghembi e non) e funzioni simmetriche di Schur. Algoritmo di Robinson-Schensted-Knuth. Riferimenti: sezioni 7.10 e 7.11. Esercizi proposti: (capitolo 7) 11, 12, 13a.
05/06/25: Identità di Cauchy, le funzioni simmetriche di Schur formano una base ortonormale. Duale dell'algoritmo di Robinson-Schensted-Knuth e duale dell'Identità di Cauchy. Definizione classica dei polinomi di Shur come bialternanti. Riferimenti: sezioni 7.12--7.15. Esercizi proposti: (capitolo 7) 28, 30, 31, 32, 37.
06/06/25: Coefficienti e regola di Littlewood-Richardson senza dimostrazioni: Teorema di Green, equivalenza di Knuth, jeu de taquin, standardizzazione. Riferimenti: appendice 7.1.