Diario delle lezioni

Alla fine di ogni lezione vengono indicati i riferimenti agli appunti, ([App]) al libro "Combinatorics of Permutations" di Miklós Bóna ([Bon]), al libro "Enumerative Combinatorics Vol I" di Richard Stanley ([Stan]), o ad altri eventuali testi suggeriti come [Appunti di Körner-Malvenuto] oppure [Appunti di Machì] i cui riferimenti precisi trovate nella sezione dei testi consigliati.

MARZO APRILE MAGGIO

1) Giovedì  25 febbraio:
Introduzione al corso: modalità  degli esami, ricevimento, libri di testo etc.
Prime definizioni: Permutazioni come ordinamenti lineari.
Discese e ascese di una permutazione. Calcolo del numero di permutazioni che hanno
un fissato insieme di discese S (o le cui discese sono contenute in S).
[Bon] Capitolo 0 e cap 1.1.1 (fino al Teorema 1.4)

2) Lunedì  1 marzo:
Enumerazione di permutazioni per insieme di discese S fissato beta(S);
enumerazione di permutazioni per discese contenute in un fissato insieme S
(Lemma 1.3) alfa(S)= prodotto di binomiali. Teorema 1.4. Calcolo di B(S) per "inclusione-esclusione".
Numeri euleriani A(n,k). Diverse notazioni.
Formula ricorsiva dei numeri euleriani. Dimostrazione combinatoria.
Simmetria dei numeri euleriani per riga fissato n.
Il monoide A^* delle parole su un alfabeto A rispetto al prodotto di concatenazione.
L'applicazione "reverse" immagine speculare è un anti automorfismo del monoide A^*
[Bon] Cap 1.1.2 fino al corollario 1.10

3) Giovedì  4 marzo:
Coefficienti binomiali (sviluppo di una produttoria in sommatoria).
Prima interpretazione combinatoria di (n su k): stringhe binarie lunghe n con k occorrenze di un fissato simbolo.
Seconda interpretrazione: sottoinsiemi di [n] con k elementi.
Identità con i binomiali: dimostrazioni combinatorie.
Simmetria dei binomiali sulla riga. Formula Ricorsiva. Formula del binomiale.
Cominciare a svolgere gli esercizi della Scheda n. 3 Capitolo
[K-M] Capitolo

4) Lunedì  2 marzo:
Coefficienti Multinomiali. Interpretazioni combinatorie con:
Stringhe k-arie, partizioni ordinate di insiemi, applicazioni da [n] a [k].
Cominciare a svolgere gli esercizi della Scheda n. 4
[K-M] Capitolo

5) Giovedì  11 marzo :
Serie generatrice dei numeri euleriani:
Teorema 1.8: x^n = somma (da 1 a n) A(n,k) bonom(x+n-k su n).
Corollario 1.10: x^n = somma (da 1 a n) A(n,k) bonom(x+n-k su n)
Formula per i numeri euleriani: Teorema 1.11
Principio di Inclusione-Esclusione.
Esercizi della Scheda n.10
[Bon] Capitolo 1.1.2
[KM] Capitolo 5.1

Lunedì  15 marzo :
Lezione cancellata per motivi di salute.

6) Giovedì  18 marzo:
P.I.E. Principle of Inclusion-Exclusion: dimostrazione. Applicazioni del P.I.E.
1. Numero di "derangements" D_n, permutazioni senza punti fissi di S_n.
2. Numero di funzioni suriettive da [n] in [m]: Sur(n,m).
3. Calcolo della funzione Phi di Eulero.
Esercizi della Scheda n. 10
[KM] Capitolo 5.1 e 5.2

7) Lunedì  22 marzo :
Esempi di suriezioni, Sur(4,2). Identità di Vandermonde.
4. Quarta applicazione del P.I.E.: formula per i numeri euleriani (teorema 1.11).
Esercizio: studiare la dimostrazione alternativa del Teorema 1.11.
Partizioni insiemistiche. Partizioni ordinate a parti non vuote:
equivalenti alle suriezioni, e alle "packed words" (parole piene).
Numeri di Stirling di seconda specie e numeri euleriani.
Cominciare a svolgere gli esercizi n 3, 4, 8, 14 pag 37 del libro, della Scheda n.
[B] Capitolo 1.1.2 e 1.1.3

8) Giovedì  25 marzo:
Numeri di Stirling di seconda specie. Teorema Formula che lega S(n,r) ai numeri euleriani.
Dimostrazione combinatoria. Corollario: formula inversa. l'Université du Littoral Côte d'Opale
Funzioni generatrici e numeri euleriani, n-simo polinomio euleriano.
Teorema: l'ennesimo polinomio euleriano è (1-x)^(n+1)\sum i?nx^i.
Funzioni generatrici. Esempio dei tilings.
Formal power series. Serie generatrice dei Fibonacci.
Esercizi della Scheda n.
[B] Capitolo 1.1.3

9) Lunedì  29 marzo :
Formula asintotica per i Fibonacci, sezione aurea.
Anello delle serie formali. Somma, prodotto, convergenza. Metodi algebrici su serie formali. Derivata di serie formali.
Versione pesata. Regole di calcolo: unione, prodotto cartesiano, liste, composizione.
Applicazioni ed esempi. Classi banali. Classe liste. Classe sottoinsiemi. Classe unione.
Cominciare a svolgere gli esercizi della Scheda n.
[FA] Appunti di Federico Ardila.

10) Giovedì  8 aprile:
Serie generatrice pesata. Serie generatrice dei multinomiali
Serie generatrice per le composizioni, versione pesata.
Composizioni a parti vincolate.
Esercizi della Scheda n.
[FA] Appunti di Federico Ardila

11) Lunedì  12 aprile :
Ancora esempi: Composizioni a parti specifiche.
Cenni ad algebre/coalgebre in combinatoria. su n
Multiinsiemi. Numero di multiinsiemi: ((m su n))= (m+n-1 su n).
Corollario ((m su n))= (m+n-1 su m-1) (dimostrazione combinatoria).
Permutazione di un multiinsieme come lattice paths su una scatola n-dimensionale.
Partizioni di intero. Varie notazioni. La serie generatrice. Diagramma di Ferrenrs di una partizione.
Cominciare a svolgere gli esercizi della Scheda n.
[] Capitolo

12) Giovedì  15 aprile:





Esercizi della Scheda n.
[] Capitolo

13) Lunedì  19 aprile :



Cominciare a svolgere gli esercizi della Scheda n.
[] Capitolo

14) Giovedì  22 aprile:





Esercizi della Scheda n.
[] Capitolo

15) Lunedì  26 aprile:



Cominciare a svolgere gli esercizi della Scheda n.
[] Capitolo

16) Giovedì  29 aprile:





Esercizi della Scheda n.
[] Capitolo

17) Lunedì  3 maggio:



Cominciare a svolgere gli esercizi della Scheda n.
[] Capitolo

18) Giovedì  6 maggio:





Esercizi della Scheda n.
[] Capitolo

29) Lunedì  10 maggio:



Cominciare a svolgere gli esercizi della Scheda n.
[] Capitolo

20) Giovedì  13 maggio:





Esercizi della Scheda n.
[] Capitolo

21) Lunedì  17 maggio:



Cominciare a svolgere gli esercizi della Scheda n.
[] Capitolo

22) Giovedì  20 maggio:





Esercizi della Scheda n.
[] Capitolo

23) Lunedì  24 maggio:



Cominciare a svolgere gli esercizi della Scheda n.
[] Capitolo

24) Giovedì  27 maggio:





Esercizi della Scheda n.
[] Capitolo