Permutazioni a motivo escluso e algoritmi di ordinamento

Si dice che una permutazione contiene un motivo π se possiede una sottosequenza isomorfa a π (nel senso dell'ordine). I risultati di natura combinatoria che riguardano gli insiemi di permutazioni che non contengono un determinato motivo (o che lo contengono un numero fissato di volte) trovano applicazione in molteplici aree, come lo studio delle singolarità delle varietà di Shuber, o la teoria dei polinomi di Chebyshev e di Kazhdan-Lustzig. Nonostante le numerose connessioni con questi problemi di natura algebrica, lo studio delle permutazioni a motivo escluso (pattern avoiding permutations) ha avuto inizio nell'ambito della teoria degli algoritmi di ordinamento: già nel primo volume di "The art of computer programming", D.E. Knuth descrisse l'insieme delle permutazioni che possono essere ordinate mediante l'utilizzo di una pila (stack sortable permutations) in termini di mancato contenimento di una sottosequenza proibita. Più recentemente sono stati caratterizzati in modo analogo alcuni insiemi di permutazioni che possono essere trasformate nell'identità dopo un numero fissato di applicazioni di alcuni tra i più celebri algoritmi di ordinamento che hanno prestazioni variabili a seconda del dato di input (come il Bubble Sort, lo Stack Sort, e le loro composizioni). In questo seminario si prende in esame il caso delle permutazioni che possono essere ordinate con una sola applicazione dell'algoritmo Cocktail Sort (che consiste nella composizione di due varianti del Bubble Sort), e si studiano le distribuzioni dei punti fissi e delle discese su tale insieme. In seguito, vengono enunciate alcune proprietà degli algoritmi di ordinamento ottenuti componendo il Cocktail Sort con lo Stack Sort.