Search

A permutation is said to avoid a pattern if it does not contain any subsequence which is order-isomorphic to it. Donald Knuth, in the first volume of his celebrated book "The art of Computer Programming", observed that the permutations that can be computed (or, equivalently, sorted) by some particular data structures can be characterized in terms of pattern avoidance. In more recent years, the topic was reopened several times, while often in terms of sortable permutations rather than computable ones. The idea to sort permutations by using one of Knuth’s devices suggests to look for a deterministic procedure that decides, in linear time, if there exists a sequence of operations which is able to convert a given permutation into the identical one. In this thesis we show that, for the stack and the restricted deques, there exists an unique way to implement such a procedure. Moreover, we use these sorting procedures to create new sorting algorithms, and we prove some unexpected commutation properties between these procedures and the base step of bubblesort. We also show that the permutations that can be sorted by a combination of the base steps of bubblesort and its dual can be expressed, once again, in terms of pattern avoidance. In the final chapter we give an alternative proof of some enumerative results, in particular for the classes of permutations that can be sorted by the two restricted deques. It is well-known that the permutations that can be sorted through a restricted deque are counted by the Schrӧder numbers. In the thesis, we show how the deterministic sorting procedures yield a bijection between sortable permutations and Schrӧder paths.

By using a symbolic method, known in the literature as the classical umbral calculus, a symbolic representation of Lévy processes is given and a new family of time-space harmonic polynomials with respect to such processes, which includes and generalizes the exponential complete Bell polynomials, is introduced. The usefulness of time-space harmonic polynomials with respect to Lévy processes is that it is a martingale the stochastic process obtained by replacing the indeterminate x of the polynomials with a Lévy process, whereas the Lévy process does not necessarily have this property. Therefore to find such polynomials could be particularly meaningful for applications. This new family includes Hermite polynomials, time-space harmonic with respect to Brownian motion, Poisson-Charlier polynomials with respect to Poisson processes, Laguerre and actuarial polynomials with respect to Gamma processes , Meixner polynomials of the first kind with respect to Pascal processes, Euler, Bernoulli, Krawtchuk, and pseudo-Narumi polynomials with respect to suitable random walks. The role played by cumulants is stressed and brought to the light, either in the symbolic representation of Lévy processes and their infinite divisibility property, either in the generalization, via umbral Kailath-Segall formula, of the well-known formulae giving elementary symmetric polynomials in terms of power sum symmetric polynomials. The expression of the family of time-space harmonic polynomials here introduced has some connections with the so-called moment representation of various families of multivariate polynomials. Such moment representation has been studied here for the first time in connection with the time-space harmonic property with respect to suitable symbolic multivariate Lévy processes. In particular, multivariate Hermite polynomials and their properties have been studied in connection with a symbolic version of the multivariate Brownian motion, while multivariate Bernoulli and Euler poly

We introduce an infinite family of lower triangular matrices ¡(s), where °s n;i counts the standard Young tableaux on n cells and with at most s columns on a suitable subset of shapes. We show that the entries of these matrices satisfy a three-term row recurrence and we deduce recursive and asymptotic properties for the total number ¿s(n) of tableaux on n cells and with at most s columns.

We define an analogue of signed Eulerian numbers fn;k for involutions of the symmetric group and derive some combinatorial properties of this sequence. In particular, we exhibit both an explicit formula and a recurrence for fn;k arising from the properties of its generating function.

La Teoria di Ramsey, che esplora le intersezioni sorprendenti tra ordine e caos, rappresenta un'area di ricerca affascinante nella Teoria dei Grafi, promettendo di svelare come, in qualsiasi sistema sufficientemente ampio e complesso, emergono inevitabilmente pattern e strutture. La presente tesi mira a guidare il lettore attraverso la Teoria di Ramsey, iniziando con un'esposizione della Teoria dei Grafi e proseguendo con un'analisi dei principi e delle applicazioni più recenti della Teoria di Ramsey. La tesi presenta un'introduzione rigorosa alla Teoria dei Grafi, esponendo le sue definizioni fondamentali, teoremi principali e problemi noti, con un focus particolare sui problemi di colorazione. Questa base teorica permette di apprezzare appieno la complessità e la bellezza intrinseche della Teoria di Ramsey quando applicata alla Teoria dei Grafi. Successivamente, il testo esplora la Teoria di Ramsey classica, discutendo la sua fondazione, i teoremi chiave, e illustrando come concetti apparentemente semplici possano avere implicazioni profonde e sorprendenti in contesti più ampi. Inoltre, la tesi approfondisce la relazione tra la Teoria dei Grafi e quella di Ramsey, esaminando come queste aree si influenzino reciprocamente e come la colorazione dei grafi riveli nuove prospettive all'interno della Teoria di Ramsey. L'analisi si conclude con uno studio sui numeri di Ramsey Arcobaleno e sulle loro applicazioni, offrendo una nuova dimensione alla discussione e mostrando l'ampio spettro di possibilità che la Teoria di Ramsey apre per la ricerca futura.

Il teorema dei quattro colori è uno dei più importanti e discussi risultati della teoria dei grafi, la cui prima formulazione risale al 1852. Si tratta, infatti, del primo teorema nella storia della matematica ad essere dimostrato tramite l'ausilio di computer, dopo innumerevoli tentativi "a mano". Due sono gli elementi fondamentali nella prima dimostrazione, pubblicata da Appel ed Haken nel 1977: il metodo di ricolorazione di Kempe ed il metodo di scarica. L'obiettivo di questa tesi è mostrare dettagliatamente l'uso del metodo di scarica in problemi di colorazione e, successivamente, fare una panoramica sul teorema dei quattro colori.

La presente tesi è suddivisa in due parti: nella prima parte illustriamo le definizioni e i relativi risultati della teoria delle tabelle di Young, introdotte per la prima volta nel 1900 da Alfred Young; mentre, nella seconda parte, diamo la nozione di numeri Euleriani e di Polinomi Euleriani. Nel primo capitolo abbiamo introdotto i concetti di diagramma di Young e di tabelle di Young standard. Inoltre, abbiamo fornito la formula degli uncini per contare le tabelle di Young della stessa forma. Il primo capitolo è focalizzato sul teorema di Robinson-Schensted, che stabilisce una corrispondenza biunivoca tra le permutazioni di Sn e le coppie di tabelle di Young standard della stessa forma. Ne deriva un'importante conseguenza che consiste nel poter trovare in modo efficiente la massima sottosequenza crescente di una permutazione. Una volta definite le operazioni di evacuazione e "le jeu de taquin" relative alle tabelle di Young, illustriamo una serie di risultati riferibili alla corrispondenza biunivoca R-S che variano in base alla permutazione che prendiamo in considerazione. In particolare, enunciamo il teorema di simmetria di M.P.Schüztenberger, che dimostriamo attraverso la costruzione geometrica di Viennot. Nel secondo capitolo, dopo aver dato la definizione di discesa di una permutazione, descriviamo altre conseguenze della corrispondenza biunivoca R-S: vediamo così che esiste una relazione tra le discese di una permutazione e la coppia di tabelle di Young associata. Abbiamo trattato approfonditamente i numeri Euleriani, indicati con A(n,k) = ]{σ ∈ Sn;d(σ) = k}, dove d(σ) indica il numero di discese di una permutazione. Descriviamo le loro proprietà e simmetrie e vediamo che sono i coefficienti di particolari polinomi, detti Polinomi Euleriani. Infine, attraverso la nozione di eccedenza di una permutazione e la descrizione della mappa di Foata arriviamo a dimostrare un importante risultato: A(n,k) conta anche il numero di permutazioni di Sn con k eccedenze.

Il tema centrale di questa tesi, suddivisa in tre capitoli, è lo studio della successione dei numeri di Catalan. Vengono mostrate le due formule della successione, quella ricorsiva e quella esplicita. Per arrivare a queste formule vengono utilizzate diverse interpretazioni per questi numeri come per esempio: le parentesi bilanciate, gli alberi, le triangolazioni di un poligono regolare convesso e i cammini di Dyck. Tali interpretazioni risulteranno essere del tutto equivalenti tra loro.

Nel corso di questa tesi è stata studiata la successione dei numeri di Catalan con particolare attenzione alla loro interpretazione in termini di cammini di Dyck. Nel primo capitolo vengono introdotti i numeri di Catalan: è riportata la storia dello studio di questa successione e le sue interpretazioni più significative da un punto di vista storico. Per dimostrare l’equivalenza di queste interpretazioni si dimostra che esse soddisfano tutte la stessa formula ricorsiva. Nel secondo capitolo vengono definiti i cammini nel piano con particolare attenzione ai cammini di Dyck; essi vengono poi utilizzati per dimostrre la formula esplicita dei numeri di Catalan in due modi differenti. Nel corso del terzo ed ultimo capitolo si utilizzano i cammini di Motzkin ed i cammini di Dyck per studiare oggetti di natura diversa: i polinomi ortogonali. Viene per questo introdotto il concetto di polinomio ortogonale, di serie dei momenti e di cammino valutato. Grazie ai cammini nel piano si calcolano, in questo capitolo, i coefficienti del teorema di Favard e si dà un’ulteriore definizione di numeri di Catalan che utilizza le matrici di Hankel.

Nel corso di questa tesi è stata studiata la successione dei numeri di Catalan con particolare attenzione alla loro interpretazione in termini di cammini di Dyck. Nel primo capitolo vengono introdotti i numeri di Catalan: è riportata la storia dello studio di questa successione e le sue interpretazioni più significative da un punto di vista storico. Per dimostrare l’equivalenza di queste interpretazioni si dimostra che esse soddisfano tutte la stessa formula ricorsiva. Nel secondo capitolo vengono definiti i cammini nel piano con particolare attenzione ai cammini di Dyck; essi vengono poi utilizzati per dimostrre la formula esplicita dei numeri di Catalan in due modi differenti. Nel corso del terzo ed ultimo capitolo si utilizzano i cammini di Motzkin ed i cammini di Dyck per studiare oggetti di natura diversa: i polinomi ortogonali. Viene per questo introdotto il concetto di polinomio ortogonale, di serie dei momenti e di cammino valutato. Grazie ai cammini nel piano si calcolano, in questo capitolo, i coefficienti del teorema di Favard e si dà un’ulteriore definizione di numeri di Catalan che utilizza le matrici di Hankel.

Nel seguente elaborato esponiamo la teoria delle matrici ricorsive, ovvero matrici doppiamente infinite in cui ogni riga può essere calcolata ricorsivamente dalla precedente e in particolare mostriamo come questa teoria possa essere utilizzata per ottenere una versione del calcolo umbrale, il quale è idoneo anche allo studio dei polinomi p(x) che assumono valori interi quando la variabile x è un intero. Studieremo alcuni dei risultati del calcolo umbrale come conseguenze delle due principali proprietà delle matrici ricorsive, ovvero la Regola del Prodotto e il Teorema della Doppia Ricorsione.

Il calcolo combinatorio è un'area della matematica ricca di applicazioni, che richiede buone capacità di modellizzazione di fenomeni di vario genere e il cui insegnamento a livello scolastico non può e, soprattutto, non deve essere banalizzato nelle soluzioni di alcuni esercizi stereotipati, come invece purtroppo accade nella maggior parte delle volte. In questa tesi si propone un percorso didattico sul calcolo combinatorio che consenta di trattarne i concetti basilari in maniera completa e sufficientemente rigorosa, con l'obiettivo, in primis, che lo studente non si trovi in difficoltà nel capire quale sia lo strumento più adatto a risolvere il problema da affrontare. Inoltre, poiché molti problemi delle Olimpiadi della Matematica riguardano il calcolo combinatorio, si vuole dare la possibilità agli alunni più portati per questa materia di sviluppare ulteriormente le loro capacità. Il percorso è integrato con laboratori pensati per dare agli studenti più confidenza con i problemi di combinatoria e mostrare loro collegamenti con altri settori, così come per favorire una comunicazione più ricca e diversificata fra loro. Inoltre, si propone un seminario di introduzione all'aritmetica modulare, rivolto agli alunni più appassionati e curiosi, e se ne mostra l'utilizzo nella risoluzione di alcuni problemi.

Il mio studio è incentrato sull'analisi dettagliata dei polinomi di Fibonacci, in particolare ho approfondito la formula ricorsiva legata ad essi, la funzione generatrice dei polinomi, la formula di Binet legata al calcolo delle radici, la sequenza delle derivate dei polinomi e la matrice che li genera. Inoltre ho trattato argomenti affini ai polinomi di Fibonacci, quali i polinomi di Lucas, analizzando in particolar modo le analogie che vi sono tra essi e le identità che li mettono in relazione tra loro, e ho accennato alla costruzione del triangolo di Tartaglia al fine di illustrare l'algoritmo che permette di calcolare i coefficienti dell'n-esimo polinomio di Fibonacci.

Questa tesi tratterà l'argomento dell'enumerazione dei cammini reticolari, ovvero una successione di punti nel reticolato euclideo dove ogni punto è determinato dal precedente aggiungendo (tramite la usuale somma termine a termine) un elemento dall'insieme dei passi. Affronteremo l'argomento avendo introdotto preliminarmente alcune restrizioni come, per esempio, l'imposizione che il cammino non entri in determinati sottoinsiemi del piano, oppure sull'insieme dei passi che vogliamo usare. Il primo capitolo è una premessa con gli strumenti principali che verranno utilizzati. Per quanto riguarda il calcolo umbrale molti dettagli sono stati omessi per favorire lo scorrimento del documento e per evitare di andare fuori argomento. Il secondo capitolo contiene alcuni tra i metodi che sono stati utilizzati per contare i cammini. Si è partiti da un problema reale, il Ballot Problem, e lo si è trasformato in un problema astratto, ovvero contare i cammini da (0,0) a (\beta, \alpha), chiedendo che l'ordinata rimanga sempre maggiore (o maggiore o uguale) di k volte l'ascissa, per un certo k intero positivo. La soluzione è stata data guardando il problema da punti di vista differenti: chi l'ha risolto dal punto di vista combinatorio, chi ha ridotto il calcolo a situazioni più semplici (usando il "metodo delle immagini" o il "lemma ciclico"), chi ha notato che una particolare applicazione del calcolo umbrale permetteva di trovare una formula per la soluzione, chi ha usato strumenti dell'analisi complessa e funzionale. Il terzo e ultimo capitolo contiene un rapido elenco di alcune successioni numeriche, e delle rispettive proprietà, che vengono generate a seconda di come scegliamo le restrizioni: i numeri di Catalan, di Narayana, di Schroeder, di Motzkin e di Delannoy.

In questa tesi si analizzano due algoritmi per la generazione di permutazioni: uno che le genera in ordine lessicografico ed un altro che genera permutazioni a motivo 231 escluso. Si ha un breve accenno ai Numeri di Catalan. Successivamente viene studiato il metodo di ordinamento di permutazioni tramite una e più pile. Infine vengono esaminate le proprietà di simmetria e unimodalità delle permutazioni ordinabili mediante t pile, con un approfondimento sugli alberi binari.

In questa tesi verrà illustrato il metodo ECO per il conteggio di classi di oggetti combinatori e, in seguito, si vedrà come applicare il metodo per il calcolo delle funzioni generatrici per le classi dei poliomini convessi ed L-convessi

Il primo capitolo di questa trattazione presenta nove differenti definizioni assiomatiche di matroide, che si dimostrano essere equivalenti attraverso il concetto di criptomorfismo. Nel secondo capitolo andremo a studiare le matroidi grafiche come esempio di matroidi. Col termine ‘matroide grafica’ indichiamo la struttura assunta da un grafo che si verifica soddisfare i vari sistemi assiomatici introdotti nel capitolo precedente. Un’attenzione particolare è data al Polinomio di Tutte, nato come oggetto definito per i grafi ed esteso successivamente alle matroidi. L’ultimo capitolo vede invece lo studio degli algoritmi greedy per le matroidi, con esempi quali l’Algoritmo di Kruskal e l’Algoritmo di Prim per la ricerca di alberi generatori di peso minimo di un grafo dato. Viene inoltre introdotto il concetto di greedoide con l’obiettivo di dimostrare che un algoritmo greedy risolve un problema di ottimizzazione se e solo se la struttura in analisi è proprio quella di un greedoide.

Questa tesi ha l'obiettivo di confrontare le performance degli algoritmi A star e bidirezionali per il problema del calcolo del cammino più breve attraverso una rete stradale. In particolare, l'analisi verte ad analizzare il numero di nodi visitati e il tempo di esecuzione degli algoritmi, su alcune mappe stradali europee morfologicamente diverse andando ad evidenziare pregi e difetti dei diversi approcci. I dati stradali sono stati ottenuti dal sito web OpenStreetMap.com, gli algoritmi presentati sono stati scritti in linguaggio Python.

Nel presente lavoro si è scelto di approfondire alcuni significativi problemi della teoria dei numeri. L'introduzione mette a punto i lavori di tre note figure dell'antichità quali Pitagora, Euclide e Diofanto riconoscendogli il ruolo di innovazionisti e maestri. Nel corpo della trattazione, l'attenzione si sofferma su quattro figure: Pierre de Fermat, Christian Goldbach, David Hilbert e Bernhard Riemann. Nell'introdurre ciascuna di queste, si è cercato di chiarire il contesto storico in cui ciascuna si è sviluppata e provare a leggere i loro lavori in chiave moderna, riportando datazione e nominativi di chi ha contribuito alla risoluzione dei vari enigmi.

In questa tesi e' stato fatto un lavoro prima creativo e poi pratico di tipologia didattica. Prima di tutto sono avvenuti degli incontri a Parma nei quali ho imparato a scrivere i giochi matematici confrontandomi con degli esperti. A questo lavoro e' seguitala creazione di una prova a cui sottoporre degli studenti delle medie. E con le conoscenze ottenute dagli incontri ho creato un compito composto da 7 esercizi con lo scopo di valutare ma soprattutto stimolare ogni parte del ragionamento matematico in un ragazzo. A questo lavoro e' seguito quello in classe dove sono stati dati i compiti e poi e' stata fatta la correzione insieme alle classi e infine la raccolta dati e il commento. Con anche l’aiuto delle insegnanti che mi hanno coinvolto nell’attivita' sia durante l’attivita' didattica che successivamente fornendo il quadro completo della classe. La tesi e' strutturata in tre parti: nel primo capitolo farò un’introduzione storica e filosofica sulla matematica e in particolare sui giochi matematici nelle scuole, spiegando nel dettaglio che cosa mi ha portato a svolgere questo lavoro. Nel secondo capitolo invece parlerò del compito stesso, di come e' stato concepito con particolare attenzione nei singoli quesiti. Infine nel terzo discuterò dei risultati ottenuti dagli studenti, guardando le percentuali di esercizi corretti e dedicando l’ultima sezione agli errori piu' comuni.