Algebre di incidenza e formula di inversione di Moebius

How to count? Per i matematici del passato, che disponevano solo di tecniche euristiche, trovare una risposta a questa domanda era tutt'altro che facile. Il principio di inclusione ed esclusione non bastava: non era, infatti, semplice né riconoscere i casi in cui questo occorreva né in tali casi applicarlo, perché mancavano tecniche generali. Per tutto il corso del diciannovesimo secolo i matematici hanno lavorato in questa direzione ma soltanto Poincaré e Fréchet hanno ottenuto risultati importanti. Nel 1964 questo vuoto fu colmato da Gian-Carlo Rota: con la teoria delle algebre di incidenza e dell'inversione di Mobius, Rota dette inizio alla sistemazione teorica e rigorosa delle tecniche combinatorie fino a quel momento utilizzate. Erano molti i problemi in combinatoria in cui occorrevano insiemi ordinati e per risolverli bisognava calcolare sommatorie indefinite che dipendevano dall'ordine. La formula di inversione ha permesso una soluzione elegante che ha aperto le strade a numerose applicazioni. L'esempio senz'altro più noto dell'uso del principio di inclusione ed esclusione è il calcolo della cardinalità dell'unione di una famiglia di insiemi: è uno dei cosidetti metodi a crivello (sieve methods), con i quali si perviene al risultato dopo una successione di somme alterne. Grazie alla teoria delle algebre di incidenza, fu possibile generalizzare il principio di inclusione ed esclusione e tutti i sieve methods, nonché la funzione di Moebius della teoria dei numeri. La stessa inversione di Mobius è una di queste procedure a crivello, dove si indicizzano le somme servendosi degli elementi del poset. Per esempio, Hardy e Wright hanno utilizzato la formula di inversione per la teoria dei numeri indicizzando le funzioni con l'insieme degli interi positivi ordinato per divisibilità. C'è da osservare che Rota non fu il primo a enunciare la formula di inversione di Mobius: infatti, essa era già comparsa nei lavori sulla teoria dei gruppi di Louis Weisner e di Philip Hall ma solo Rota ne ha colto gli aspetti di natura combinatoria, sviluppandoli nella sua teoria. In questa tesi si presenta la teoria dell'inversione di Mobius-Rota su insiemi parzialmente ordinati, con particolare riferimento alle applicazioni combinatorie. Si esplorano, inoltre, le connessioni tra le funzioni generatrici e le funzioni moltiplicative dell'algebra di incidenza di una classe particolare di poset localmenti finiti: i poset binomiali.