Combinatoria

János Körner Claudia Malvenuto 21 ottobre 2009

2

Prefazione

Caro Lettore,

gli appunti di queste pagine contengono tutto il materiale spiegato durante le lezioni e parte del materiale relativo alle esercitazioni del corso Matematica Discreta 1: Combinatoria impartito per il Corso di Laurea in Informatica dell’Università di Roma La Sapienza. Il materiale è stato scelto quasi integralmente dai primi capitoli dell’eccellente libro di J. H. van Lint e R. M. Wilson, A Course in Combinatorics [?]. Il libro di van Lint e Wilson nasce dalle loro lezioni presso il California Institute of Technology. Bisogna ammettere che il testo di van Lint-Wilson è destinato ad un pubblico che possiede una maggiore esperienza matematica di quella di uno studente di secondo anno del nostro Corso di Laurea. Questo spiega però solo in parte il carattere compatto delle dimostrazioni fornite dagli autori di [?]. La forma abbozzata delle loro dimostrazioni è soprattutto frutto della loro ambizione di costringere lo studente ad una lettura autonoma, attiva ed approfondita del loro libro. Ciò significa che il lettore deve completare il testo delle loro dimostrazioni, come e più di quanto si fa solitamente per risolvere i familiari esercizi nei libri di grammatica. Difatti la matematica non si capisce leggendo un testo con le mani in mano. È quindi con molta esitazione e quasi malvolentieri che si offre oggi alla lettura dei nostri studenti il seguente testo in cui ogni dubbio lasciato aperto, ogni piccolo salto logico del libro [?] è cancellato. Lo studente che malauguratamente fosse interessato solo a superare l’esame di Combinatoria senza cercare di capire la materia potrebbe essere tentato di memorizzare questo testo. Nulla di più sbagliato.

Naturalmente, non ci siamo limitati a completare le dimostrazioni in [?]. In alcuni casi le abbiamo modificate, e inoltre abbiamo aggiunto altro materiale (come per esempio quello sulla decomposizione ciclica delle permutazioni.) Il nostro testo non ha certo l’ambizione di essere un libro sulla Combinatoria. L’esposizione segue quasi pedissequamente le deduzioni matematiche esposte alla lavagna durante il corso e i commenti rimangono essenziali. È nostra ferma convinzione che un corso introduttivo non deve limitarsi alla presentazione di fatti e dimostrazioni elementari, con il rischio di banalizzare la materia. Al contrario, per convincere lo studente del potere e della bellezza dei metodi e dei risultati della combinatoria, è indispensabile sorprenderlo e poi coinvolgerlo in imprese matematiche serie. Abbiamo quindi preferito alla redazione di un catalogo enciclopedico di concetti e lemmi elementari e di routine l’esposizione di pochi risultati e metodi importanti. Anzi, abbiamo utilizzato proprio questi risultati per introdurre alcuni dei più salienti concetti della combinatoria in un contesto dimostrativo che li mette alla ribalta. Il materiale qui presentato non è esposto a lezione tutti gli anni. Di anno in anno, sarà il programma del Corso a specificare quella parte del testo che si deve studiare per l’esame.

La teoria combinatoria è il principale strumento matematico di quella parte dell’informatica teorica che riguarda la costruzione di algoritmi e l’analisi della loro complessità. Eppure in Italia non tutti i corsi di laurea in informatica offrono un corso di combinatoria. Il nostro manoscritto è poco più che un invito a insegnare e studiare questa materia, rivolta a studenti di informatica e matematica. Questa ne è la prima versione, ed è destinata a crescere, anche con il vostro aiuto. Ogni commento e critica è decisamente benvenuto, anche qualora si limiti soltanto a segnalarci gli inevitabili errori di stampa.

Vogliamo ringraziare Gabriele Mambrini il quale, producendo un primo manoscritto in L^{A}TEX di appunti di questo corso, ha fornito un canovaccio e uno stimolo di partenza per la redazione del presente testo; gli studenti Cecilia di Chio e Fabio Martinelli per aver messo a disposizione le fotocopie dei loro appunti, presi durante l’anno accademico 2000/01. Ringraziamo inoltre il dott. Daniele A. Gewurz che dopo aver letto con estrema attenzione (e pignoleria!) questo testo ci ha segnalato vari refusi e suggerito utili modifiche.

János Körner^{1} Claudia Malvenuto^{2}

1korner@di.uniroma1.it

2claudia@di.uniroma1.it

Indice

iii iv INDICE