La combinatoria analitica può definirsi come il settore della combinatoria che affronta i problemi delle configurazioni discrete mediante le tecniche ed il linguaggio delle serie generatrici; in particolare si utilizzano acquisizioni dell'analisi complessa per ottenere dei risultati sul comportamento asintotico delle cardinalità di configurazioni combinatorie. Molti risultati della combinatoria analitica forniscono strumenti efficaci per lo studio della complessità di vari algoritmi.
Introduzione La combinatoria analitica si organizza intorno a varie tematiche. Si impiegano dei metodi simbolici per esprimere relazioni tra oggetti matematici discreti ed operazioni algebriche sopra funzioni generatrici con scopi enumerativi; si sviluppano invece dei metodi di analisi complessa al fine di ricavare dalle funzioni generatrici delle informazioni sul comportamento asintotico del numero degli oggetti enumerati; nella natura delle singolarità si cerca la chiave per lo studio dei comportamenti asintotici. Inoltre una importante attività si rivolge allo studio delle proprietà probabilistiche delle grandi strutture aleatorie.
La combinatoria analitica è stata ampiamente sviluppata negli ultimi decenni, soprattutto per merito di Philippe Flajolet e dalla sua scuola. Essa è stata presentata in modo dettagliato e completo nel libro Analytic Combinatorics scritto da lui e da Robert SedgewickPhilip Flajolet, Robert Sedgewick (2009): Analytic Combinatorics, Cambridge University Press, ISBN 978-0-521-89806-5 - accessibile in . Dei precedenti contributi a questo approccio possono essere trovati nei lavori di Leonhard Euler, Arthur Cayley, Srinivasa Ramanujan, George Pólya e Donald Knuth.
Classi combinatorie I metodi simbolici si concentrano sulla nozione di classe combinatoria, cioè sugli insiemi delle configurazioni (o strutture) finite ciascuna delle quali è caratterizzata da un intero naturale che esprime una sua taglia. Questi metodi consistono nell'associare alle operazioni insiemistiche o algebriche riguardanti le classi delle operazioni algebriche sulle riguardanti corrispondenti serie generatrici in modo da ottenere un processo di traduzione puramente formale tra proprietà delle classi e proprietà delle serie. Si constata che vi sono due tipi di funzioni generatrici assai proficui per operare con la detta corrispondenza, le funzioni generatrici ordinarie da associare alle classi di configurazioni non etichettate e le funzioni generatrici esponenziali per le classi delle configurazioni etichettate.
Definizioni
Diciamo classe combinatoria un insieme munito di un'applicazione che chiamiamo taglia. Per ogni elemento dell'insieme scriviamo l'intero naturale che costituisce la sua taglia. Si chiede inoltre che per ogni taglia il numero di elementi di tle taglia sia finito.
Per le funzioni taglia delle specie di configurazioni più usuali si impongono come più promettenti alcune definizioni in grado di rappresentare con chiarezza il grado di estensione (o di peso, o di ricchezza, o di complessità) delle singole configurazioni. Ad esempio come taglia degli alberi binari si può assumere il numero dei loro vertici; ma un'altra scelta promettente può consistere nella loro altezza. Non è invece lecito assumere il numero delle loro foglie, in quanto il numero degli alberi binari con dato numero di foglie non è finito: si pensi che ogni albero binario si può allungare senza limiti aggiungendogli nodi con un solo successore. In generale ogni configurazione caratterizzata da una taglia si può considerare ottenuto componendo opportunamente delle componenti elementari che si usano chiamare atomi: un esempio è dato dai nodi di un grafo, un altro dalle lettere delle stringhe di un insieme caratterizzato da qualche vincolo.
Consideriamo ora un insieme combinatorio e denotiamo con il numero degli elementi di tale insieme aventi taglia . Si definisce come serie generatrice ordinaria nella variabile formale associata ad la serie definita come . Spesso è comodo servirsi di una seconda espressione equivalente per questa serie: .
Per le specie di strutture etichettate considereremo invece più delle cosiddette serie generatrici esponenziali.
In genere le serie generatrici associate alla enumerazione degli oggetti combinatori sono serie formali, entità che si trattano senza porsi problemi di convergenza. Nell'ambito della combinatoria analitica, invece, si studiano i comportamenti delle serie nel quadro dell’analisi complessa. L'osservazione fondamentale che si utilizza, come esplicitato di seguito, riguarda il fatto che la natura della singolarità sull'asse reale positivo fornisce informazioni precise sulla crescita dei numeri degli oggetti di taglia .
Conviene introdurre una notazione utile per esprimere i coefficienti di una serie generatrice : scriveremo per denotare il coefficiente della variabile , in modo che per , si abbia: .
Esempi Presentiamo alcuni esempi riguardanti configurazioni piuttosto note. Classe delle parole su un alfabeto di due lettere assumendo con taglia la lunghezza delle parole. Vi sono parole di lunghezza e la serie generatrice è
Composizioni di interi positivi, intendendo che le composizioni di sono tutte le sequenze di interi positivi tali che . Il numero delle composizioni di è e la serie generatrice è
Il numero degli alberi binari completi con nodi è e la relativa serie generatrice è .
Il metodo simbolico Il metodo simbolico è un procedimento che si propone di tradurre direttamente relazioni tra classi combinatorie nelle serie generatrici corrispondenti. Si procede secondo un algoritmo che inizia con classi combinatorie molto semplici e le compone servendosi di operatori dal comportamento noto. Questi operatori insiemistici riguardano, oltre che operazioni semplici come l'unione disgiunta, il prodotto cartesiano, altre operazioni un po' più complesse, come il passaggio all'insieme delle parti, la formazione di sequenze e di multiinsiemi. Inoltre si possono far intervenire costruzioni ricorsive. Il vantaggio di questo metodo consiste nel fatto che la definizione insiemistica, o simbolica, conduce direttamente a relazioni algebriche sopra le funzioni generatrici.
Di solito in combinatoria si utilizzano due tipi di serie generatrici, le serie generatrici ordinarie, da applicare alle classi combinatorie di oggetti non etichettati, e le serie generatrici esponenziali, per le classi combinatorie di oggetti etichettati.
Nelle esposizioni della combinatoria si usa denotare le classi combinatorie con lettere in corsivo e le loro serie generatrici con le corrispondenti lettere in fonti dritte. Ad esempio le serie associate alla classe combinatoria , alla ed alla sono denotate, rispettivamente, con e .
Costruzioni elementari Come mattoni di base si assumono delle classi formate da un solo oggetto. Si rivelano utili due tipi di classi: quelle nelle quali al singoletto si attribuisce taglia zero e quelle il cui singoletto assume taglia uno. Una classe del primo tipo dunque presenta un elemento di taglia nulla e la sua serie generatrice è la funzione costante . Una classe del secondo tipo ha un solo elemento, di taglia uno, e la sua serie generatrice è . Le operazioni elementari sono l'unione disgiunta, il prodotto cartesiano e la formazione di sequenze.
Unione disgiunta Scriviamo per denotare la classe che è unione disgiunta delle classis e . Questa relazione si traduce per le serie generatrici nella , in quanto .
Prodotto cartesiano Si scrive se la classe è l'insieme delle coppie , con e . La funzione taglia è definita dalla . Per le corrispondenti serie generatrici si ha quindi la relazione .
Sequenze Scriviamo quando è l'insieme delle sequenze finite di elementi di . In altri termini , o anche . La taglia di una sequenza è la somma delle taglie delle sue componenti. Perché l’operazione sia ben definita, la classe non deve contenere alcun elemento di taglia 0; in caso contrario la classe conterrebbe une infinità di elementi di una qualsiasi taglia positiva. La traduzione nelle serie generatrici est . La serie viene talora chiamata la quasi-inversa della serie .
Definizione ricorsiva Quando sono soddisfatte certe condizioni piuttosto tecniche , si possono introdurre classi combinatorie con definizioni ricorsive. Limitiamoci a presentare alcuni esempi.
Alberi binari Per albero binario intendiamo sia l'insieme vuoto che chiamiamo albero vuoto, sia un grafo formato da un vertice radice e da due suoi sottoalberi ai quali a loro volta chiediamo siano alberi binari. L'equazione della classe combinatoria degli alberi binari è dunque: , dove è costituita da un solo elemento di taglia 0 e è composta da un solo elemento di taglia 1. Questa equazione si traduce nell’equazione .
Alberi unari-binari Un albero unario-binario è un albero nel quale ogni suo nodo interno, nodo non foglia, possiede uno o due discendenti. La corrispondente equazione simbolica ha la forma
e da questa si deduce l'equazione funzionale .
Esempi Si può adoperare il metodo simbolico anche nei tre casi elementari che seguono.
Parole binarie Una parola binaria è une sequenza di simboli 0 e 1. Introduciamo due semplicissime classi combinatorie e , entrambe aventi come serie generatrice la . Le parole binarie si ottengono con la costruzione , e la serie generatrice di questi oggetti è e . Va riconosciuto che per un esempio molto semplice si è utilizzato un grosso apparato formale. Composizione ristretta di interi Consideriamo il problema di coprire il segmento con dei mattoni di estensione (taglia) 1 e 2; in altre parole si tratta di scrivere l'intero come somma di addendi uguli a 1 o 2; si vuole poi conoscere in quanti modi si può far questo, cioè il numero delle coperture di . Per esempio, l'intero 4 può ottenersi con cinque scritture: 4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2 . Si constata facilmente che il numero delle composizioni di è , l'-esimo numero de Fibonacci. Per giungervi con il metodo simbolico si considerano due classi e formate da un unico elemento avente, rispettivamente taglia 1 e taglia 2. Con queste classi la classe delle coperture est
e la corrispondente serie generatrice è: .
Altre costruzioni simboliche Vediamo altre costruzioni simboliche importanti. Cicli. I cicli, il cui insieme denotiamo con , sono simili alle sequenze, salvo che due oggetti che si ottengono l'uno dall'altro mediante una rotazione circolare non sono considerati distinti. La serie generatrice dei cicli è nettamente più complicata; il caso dei cicli etichettati porta ad una serie più semplice:
ove è la indicatrice di Eulero. Classe puntata. Si denota con la classe degli insiemi di elementi di tra i quali uno è «puntato», ovvero contrassegnato in modo da risultare distinto dagli altri. Per esempio, gli alberi muniti di radice sono alberi liberi puntati. Formalmente, ogni oggetto è arricchito da un elemento de taglia zero sopra uno dei suoi componenti (atomi). La serie generatrice è . Sostituzione. La classe si ottiene sostituendo, ogni atomo di un elemento di , un elemento della classe . La serie generatrice si esprime semplicemente con .
Analisi I metodi di analisi complessa ruotano intorno al processo di estrazione di informazioni asintotiche dalle funzioni generatrici. Si è raggiunto un insieme di risultati che garantiscono la fattibilità di una traduzione sistematica tra funzioni generatrici e la forma asintotica dei coefficienti.
Nella maggior parte delle situazioni che si presentano in combinatoria, una serie formale con capacità enumerativa
può essere vista come lo sviluppo intorno allo 0 di una funzione analitica . Il raggio di convergenza della serie è ottenibile, ad esempio, come par . Questo significa che )