Combinatoria analitica

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 Sedgewick. 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 ${\mathcal {A}}$ munito di un'applicazione $|\cdot |:{\mathcal {A}}\to \mathbb {N}$ che chiamiamo taglia. Per ogni elemento $a$ dell'insieme ${\mathcal {A}}$ scriviamo $|a|$ l'intero naturale che costituisce la sua taglia. Si chiede inoltre che per ogni taglia $n$ 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 ${\mathcal {A}}$ e denotiamo con $a_{n}$ il numero degli elementi di tale insieme aventi taglia $n$. Si definisce come serie generatrice ordinaria nella variabile formale $z$ associata ad ${\mathcal {A}}$ la serie definita come

$A(z)=\sum _{n=0}^{\infty }a_{n}z^{n}$.

Spesso è comodo servirsi di una seconda espressione equivalente per questa serie:

$A(z)=\sum _{a\in {\mathcal {A}}}z^{|a|}.$.

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 $a_{n}$ degli oggetti di taglia $n$.

Conviene introdurre una notazione utile per esprimere i coefficienti di una serie generatrice $f(z)$ : scriveremo $[z^{n}]$ per denotare il coefficiente della variabile $z^{n}$, in modo che per

$f(z)=\sum _{n=0}^{\infty }f_{n}z^{n}$,

si abbia:

$[z^{n}]f(z)=f_{n}$.

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 $2^{n}$ parole di lunghezza $n$ e la serie generatrice è

${\frac {1}{1-2z}}$

• Composizioni di interi positivi, intendendo che le composizioni di $n$ sono tutte le sequenze di interi positivi $(p_{1},p_{2},\ldots ,p_{r})$ tali che $p_{1}+p_{2}+\cdots +p_{r}=n$. Il numero delle composizioni di $n$ è $2^{n-1}$ e la serie generatrice è

${\frac {z}{1-2z}}$

• Il numero degli alberi binari completi con $n$ nodi è

${\frac {1}{n+1}}{\binom {2n}{n}}$ e la relativa serie generatrice è

${\frac {1-{\sqrt {1-4z}}}{2z}}$.

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 ${\mathcal {A}}$, alla ${\mathcal {B}}$ ed alla ${\mathcal {C}}$ sono denotate, rispettivamente, con $A(z),B(z)$ e $C(z)$.

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 ${\mathcal {E}}=\{\varepsilon \}$ del primo tipo dunque presenta un elemento $\varepsilon$ di taglia nulla e la sua serie generatrice è la funzione costante $E(z)=1$. Una classe ${\mathcal {Z}}=\{z\}$ del secondo tipo ha un solo elemento, di taglia uno, e la sua serie generatrice è $Z(z)=z$. Le operazioni elementari sono l'unione disgiunta, il prodotto cartesiano e la formazione di sequenze.

Unione disgiunta

Scriviamo ${\mathcal {A}}={\mathcal {B}}+{\mathcal {C}}$ per denotare la classe ${\mathcal {A}}$ che è unione disgiunta delle classis ${\mathcal {B}}$ e ${\mathcal {C}}$. Questa relazione si traduce per le serie generatrici nella

$A(z)=B(z)+C(z)$ ,

in quanto

$A(z)=\sum _{a\in {\mathcal {A}}}z^{|a|}=\sum _{b\in {\mathcal {B}}}z^{|b|}+\sum _{c\in {\mathcal {C}}}z^{|c|}=B(z)+C(z)$.

Prodotto cartesiano

Si scrive ${\mathcal {A}}={\mathcal {B}}\times {\mathcal {C}}$ se la classe ${\mathcal {A}}$ è l'insieme delle coppie $a=(b,c)$, con $b\in {\mathcal {B}}$ e $c\in {\mathcal {C}}$. La funzione taglia è definita dalla $|a|=|b|+|c|$. Per le corrispondenti serie generatrici si ha quindi la relazione

$A(z)=B(z)C(z)$.

Sequenze

Scriviamo ${\mathcal {A}}={\mathsf {Seq}}({\mathcal {B}})$ quando ${\mathcal {A}}$ è l'insieme delle sequenze finite di elementi di ${\mathcal {B}}$. In altri termini

${\mathcal {A}}={\mathcal {E}}+{\mathcal {B}}+{\mathcal {B}}\times {\mathcal {B}}+{\mathcal {B}}\times {\mathcal {B}}\times {\mathcal {B}}+\cdots$, o anche ${\mathcal {A}}=\{(b_{1},\ldots ,b_{h})\mid h\geq 0,b_{j}\in {\mathcal {B}}\}$.

La taglia di una sequenza $(b_{1},\ldots ,b_{h})$ è la somma delle taglie delle sue componenti. Perché l’operazione sia ben definita, la classe ${\mathcal {B}}$ non deve contenere alcun elemento di taglia 0; in caso contrario la classe ${\mathcal {A}}$ conterrebbe une infinità di elementi di una qualsiasi taglia positiva. La traduzione nelle serie generatrici est

$A(z)={\frac {1}{1-B(z)}}$.

La serie $A(z)$ viene talora chiamata la quasi-inversa della serie $B(z)$.

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 ${\mathcal {B}}$ degli alberi binari è dunque:

${\mathcal {B}}={\mathcal {E}}+{\mathcal {Z}}\times {\mathcal {B}}\times {\mathcal {B}}$, dove

${\mathcal {E}}$ è costituita da un solo elemento di taglia 0 e ${\mathcal {Z}}$ è composta da un solo elemento di taglia 1. Questa equazione si traduce nell’equazione

$B(z)=1+zB(z)^{2}$.

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

${\mathcal {U}}={\mathcal {Z}}+{\mathcal {Z}}\times {\mathcal {B}}+{\mathcal {Z}}\times {\mathcal {B}}\times {\mathcal {B}}$

e da questa si deduce l'equazione funzionale

$U(z)=z+zU(z)+zU(z)^{2}.$.

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 ${\mathcal {Z}}_{0}=\{0\}$ e ${\mathcal {Z}}_{1}=\{1\}$, entrambe aventi come serie generatrice la $z$. Le parole binarie si ottengono con la costruzione

${\mathcal {W}}_{0}={\mathsf {Seq}}({\mathcal {Z}}_{0}+{\mathcal {Z}}_{1})$,

e la serie generatrice di questi oggetti è

$W(z)={\frac {1}{1-(z+z)}}$ e $[z^{n}]W(z)=2^{n}$.

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 $[0,n]$ con dei mattoni di estensione (taglia) 1 e 2; in altre parole si tratta di scrivere l'intero $n$ 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 $[0,n]$ . 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 $n$ è $F_{n}$, l'$n$-esimo numero de Fibonacci. Per giungervi con il metodo simbolico si considerano due classi ${\mathcal {Z}}_{1}$ e ${\mathcal {Z}}_{2}$ formate da un unico elemento avente, rispettivamente taglia 1 e taglia 2. Con queste classi la classe delle coperture est

${\mathcal {F}}={\mathsf {Seq}}({\mathcal {Z}}_{1}+{\mathcal {Z}}_{2})$

e la corrispondente serie generatrice è:

$F(z)={\frac {1}{1-z-z^{2})}}=1+z+2z^{2}+3z^{3}+5z^{4}+\cdots$.

Altre costruzioni simboliche

Vediamo altre costruzioni simboliche importanti. Cicli. I cicli, il cui insieme denotiamo con ${\mathcal {A}}={\mathsf {Cyc}}({\mathcal {B}})$, 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:

$A(z)=\sum _{k=1}^{\infty }{\frac {\phi (k)}{k}}\log {\frac {1}{1-B(z^{k})}}$

ove $\phi (k)\,$ è la indicatrice di Eulero. Classe puntata. Si denota con $\Theta {\mathcal {B}}$ la classe degli insiemi di elementi di ${\mathcal {B}}$ 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 è

$z{\frac {\partial }{\partial z}}B(z)$.

Sostituzione. La classe ${\mathcal {B}}\circ {\mathcal {C}}$ si ottiene sostituendo, ogni atomo di un elemento di ${\mathcal {B}}$, un elemento della classe ${\mathcal {C}}$. La serie generatrice si esprime semplicemente con $B(C(z))$.

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

$f(z)=\sum _{n\geq 0}f_{n}z^{n}$

può essere vista come lo sviluppo intorno allo 0 di una funzione analitica $f(z)$. Il raggio di convergenza $R$ della serie è ottenibile, ad esempio, come par

$1/R=\limsup |f_{n}|^{1/n}$.

Questo significa che

$f_{n}\sim R^{-n}\theta (n)$)

dove $\theta (n)$ è una funzione sub-esponenziale di $n$. Quindi sul raggio di convergenza si trova una singolarità ed un teorema classico di Pringsheim (da non confondere con un teorema de Pringsheim dello stesso nome) afferma che se i coefficienti $f_{n}$ sono non negativi, come evidentemente accade alle serie enumeratrici, allora esiste una singolarità reale positiva nel punto $z=R$.

Caso delle serie razionali

Con i costruttori diversi dalla ricorsività, cioè con ${\mathcal {E}},{\mathcal {Z}}$ e con gli operatori $+,\times ,{\mathsf {Seq}}$, si ottengono le serie razionali. In tal caso il termine $f_{n}$ è asintoticamente equivalente ad una somma di termini della forma $cn^{k}R^{-n}$. Più precisamente, se la singolarità dominante presenta molteplicità $k$, allora

$[z^{n}]f(z)\sim {\frac {R^{-n}n^{k}}{k!}}$.

Esempio.- Consideriamo la serie razionale

$f(z)=(1-z^{2}/2)^{-5}(1-z^{3})^{-1}(1-2z)^{-5}(1-z-z^{2})^{-1}$.

Le sue singolaritàsi trovanoo in ${\sqrt {2}},-{\sqrt {2}},1,1/2,\phi ,{\bar {\phi }}$ ($\phi$ denota la sezione aurea). La singolarità dominante è 1/2, e la sua molteplicità è 5. Quindi si ha

$[z^{n}]f(z)\sim {\frac {1}{4!}}2^{n}n^{4}$.

Un caso più generale

Il caso generale è più delicato e procede nel modo che segue. Si consideri une famiglia generale ma ben precisa di funzioni (combinazioni di potenze (complesse) di $(1-z)$ e di $\log(1-z)$); per esse si sanno ottenere delle stime asintotiche servendosi degli strumenti di analisi complessa più o meno impegnativi. Successivamente si utilizza un altro principio di base, chiamato teorema di transfert, che in parole povere dice che se due funzioni sono «vicine» in un intorno di una loro singolarità reale, sono vicini anche i loro rispettivi coefficienti. Il risultato sulla famiglia di funzioni presentato limitandoci al caso della singolarità nel punto 1 (al quale ci si può sempre ricondurre con un semplice cambiamento di variabile) è il seguente.

Consideriamo $\alpha \in \mathbb {R} \setminus \{0,-1,-2,\ldots \}$ e $k\in \mathbb {N}$. Abbiamo allora

$[z^{n}]{\frac {1}{1-z)^{\alpha }}}\log ^{k}\left({\frac {1}{1-z}}\right)\sim {\frac {n^{\alpha -2}}{\Gamma (\alpha )}}\log ^{k}(n)$,

dove $\Gamma$ denota la classica funzione Gamma.

Presentiamo alcuni dei molti esempi contenuti nel libro di Flajolet e Sedgewick.

Funzione	Coefficienti
$(1-z)^{3/2}$	${\frac {1}{\sqrt {\pi n^{5}}}}{\bigl (}{\frac {3}{4}}+{\frac {45}{32n}}+{\frac {1155}{512n^{2}}}+O{\bigl (}{\frac {1}{n^{3}}}{\bigr )}{\bigr )}$
$(1-z)^{1/2}$	$-{\frac {1}{\sqrt {\pi n^{3}}}}{\bigl (}{\frac {1}{2}}+{\frac {3}{16n}}+{\frac {25}{256n^{2}}}+O({\frac {1}{n^{3}}}){\bigr )}$
$(1-z)^{1/2}\log(1-z)$	$-{\frac {1}{\sqrt {\pi n^{3}}}}{\bigl (}{\frac {1}{2}}\log n+{\frac {\gamma +2\log 2-2}{2}}+O{\bigl (}{\frac {\log n}{n}}{\bigr )}{\bigr )}$
$(1-z)^{-1/2}$	${\frac {1}{\sqrt {\pi n}}}{\bigl (}1-{\frac {1}{8n}}+{\frac {1}{128n^{2}}}+{\frac {5}{1024n^{3}}}+O{\bigl (}{\frac {1}{n^{4}}}{\bigr )}{\bigr )}$
$(1-z)^{-1/3}$	${\frac {1}{\Gamma (1/3)n^{2/3}}}{\bigl (}1+O{\bigl (}{\frac {1}{n}}{\bigr )}{\bigr )}$
$(1-z)^{-1}\log ^{2}(1-z)$	$\log ^{2}n+2\gamma \log n+\gamma ^{2}-{\frac {\pi ^{2}}{6}}+O{\bigl (}{\frac {\log n}{n}}{\bigr )}$

Il teorema di transfert

Il teorema di transfert afferma che basta conoscere il comportamento di due funzioni in un intorno della loro più piccola singolarità per essere in grado di confrontare il comportamento asintotico dei loro coefficienti. Un suo enunciato è il seguente.

Siano $f(z)$ e $g(z$) due funzioni aventi la più piccola singolarità in 1. Allora:

da   $f(z)\sim _{z\to 1}g(z)$   segue   $f_{n}\sim g_{n}$ ;

da   $f(z)=_{z\to 1}O(g(z))$   segue   $f_{n}=O(g_{n})$ ;

da   $f(z)=_{z\to 1}o(g(z))$   segue   $f_{n}=o(g_{n})$ .

Un esempio

Procediamo alla valutazione asintotica del numero degli alberi binari. Si inizia dalla equazione simbolica

${\mathcal {B}}={\mathcal {E}}+{\mathcal {Z}}\times {\mathcal {B}}\times {\mathcal {B}}$,

dove ${\mathcal {E}}$ è ridotto ad un elemento di taglia 0 e ${\mathcal {Z}}$ è composto da un elemento di taglia 1. Questa equazione si traduce nell'equazione

$B(z)=1+zB(z)^{2}$.

Si risolve questa equazione trovano

$B(z)={\frac {1-{\sqrt {1-4z}}}{2z}}$.

La funzione presenta una singolarità in $z=1/4$ avente ordine $-1/2$. In un intorno di $z=1/4$ si può scrivere

$B(z)\sim {\frac {2}{(1-4z)^{1/2}}}$

e grazie al teorema generale, dato che $\Gamma (-1/2)=-2{\sqrt {\pi }}$, si ottiene

$[z^{n}]B(z)\sim -2{\frac {4^{n}n^{-3/2}}{\Gamma (-1/2)}}={\frac {4^{n}n^{-3/2}}{\sqrt {\pi }}}$ .

Classi combinatorie etichettate

Une classe combinatoria si dice etichettata se i suoi elementi sono etichettati. Per definizione un tale oggetto combinatorio di taglia $n$, è di più dotato di una permutazione dell'insieme $\{1,\ldots ,n\}$. Gli esempi più pertinenti di oggetti etichettati sono i grafi.

Per enumerare gli oggetti di una classe etichettata si adoperano serie generatrici esponenziali, serie i cui coefficienti sono normalizzati dal fattoriale del grado (taglia).

Definizione

Più formalmente, sia ${\mathcal {A}}$ una classe combinatoria etichettata, e sia $a_{n}$, per $n\geq 0$, il numero degli oggetti di questa classe aventi taglia $n$. La serie generatrice esponenziale associata ad ${\mathcal {A}}$ ha la forma

$A(z)=\sum _{n=0}^{\infty }a_{n}{\frac {z^{n}}{n!}}$.

Questo equivale a scrivere

$A(z)=\sum _{a\in {\mathcal {A}}}{\frac {z^{|a|}}{|a|!}}$ .

L'estrazione di un coefficiente da questa serie fornisce

$[z^{n}]A(z)={\frac {a_{n}}{n!}}$; dunque $a_{n}=n![z^{n}]A(z)$.

Esempi

Permutazioni. Denotiamo con ${\mathcal {P}}$ la classe delle permutazioni. Sa serie generatrice esponenziale è

$P(z)=\sum _{n\geq 0}n!{\frac {z^{n}}{n!}}={\frac {1}{1-z}}$.

Grafi senza spigoli. Per ogni intero $n$ esiste uno e un solo grafo senza spigoli e la corrispondente serie generatrice è

$\sum _{n\geq 0}{\frac {z^{n}}{n!}}=e^{z}$

La stessa serie enumera i grafi completi.

Grafi ciclici. Il numero dei grafi etichettati con $n$ vertici collegati in modo da formare un solo cicle è (n-1)!. La loro serie generatrice esponenziale è pertanto

$\sum _{n\geq 0}(n-1)!{\frac {z^{n}}{n!}}=\sum _{n\geq 0}{\frac {z^{n}}{n}}=\log {\bigl (}{\frac {1}{1-z}}{\bigr )}$.

Costruzioni

Prodotto

La costruzione di una somma disgiunta di classi combinatorie si traspone senza modifiche alle classi etichettate. Per il prodotto la trasformazione è più delicata. Siano ${\mathcal {B}}$ e ${\mathcal {C}}$ due classi combinatorie etichettate. Il loro prodotto cartesiano è costituito dalle coppie $(b,c)$ di oggetti etichettati, ma una di queste coppie non è etichettata soddisfacentemente, in quanto i suoi elementi non presentano etichette distinte. Occorre definire una struttura $(b',c')$ associata, ai cui elementi si attribuiscono le etichette $\{1,\ldots ,|b|+|c|\}$, in modo che l'ordine relativo delle etichette di ogni elemento è rispettata. Si definisce

$b\star c$

come l'insieme delle coppie $(b',c')$ così rietichettate. La famiglia $b\star c$ contiene esattamente ${\binom {|b|+|c|}{|b|}}$ elementi. Il prodotto etichettato delle classi ${\mathcal {B}}$ e ${\mathcal {C}}$ viene definito

${\mathcal {A}}:={\mathcal {B}}\star {\mathcal {C}}=\bigcup _{b\in {\mathcal {B}},c\in {\mathcal {C}}}b\star c$.

Per le serie generatrici esponenziali si ottiene

$A(z)=B(z)C(z)$.

In effetti, per $b\in {\mathcal {B}}$ e $c\in {\mathcal {C}}$, si ha

$\sum _{a\in b\star c}{\frac {z^{|a|}}{|a|!}}=\sum _{a\in b\star c}{\frac {z^{|b|+|c|}}{|b|+|c|!}}={\binom {|b|+|c|}{|b|}}{\frac {z^{|b|+|c|}}{|b|+|c|!}}={\frac {z^{|b|}}{|b||!}}{\frac {z^{|c|!}}{|c|!}}$,

et quindi

$A(z)=\sum _{a\in {\mathcal {A}}}{\frac {z^{|a|}}{|a|!}}=\sum _{b\in {\mathcal {B}}}\sum _{c\in {\mathcal {C}}}{\frac {z^{|b|}}{|b|!}}{\frac {z^{|c|!}}{|c|!}}=B(z)C(z)$.

Sequenza

A partire dalla somme disgiunta e dal prodotto, si costruisce l'operatore di sequenza come nel caso ordinario. Per l'insieme delle sequenze finite di elementi di ${\mathcal {B}}$ scriviamo ${\mathcal {A}}={\mathsf {Seq}}({\mathcal {B}})$. Va notato che ${\mathcal {B}}$ non presenta alcun elemento di taglia nulla. In altri termini

${\mathcal {A}}={\mathcal {E}}+{\mathcal {B}}+{\mathcal {B}}\times {\mathcal {B}}+{\mathcal {B}}\times {\mathcal {B}}\times {\mathcal {B}}+\cdots$,

o ancore ${\mathcal {A}}=\{(b_{1},\ldots ,b_{h})\mid h\geq 0,b_{j}\in {\mathcal {B}}\}$, dove le sequenze sono rietichettate. Per la serie generatrice esponenziale si ha

$A(z)=\sum _{h\geq 0}B(z)^{h}={\frac {1}{1-B(z)}}$.

Insieme delle parti

Le definizioni d'insieme e di ciclo date in precedenza si adattano anche alle strutture non etichettate. Si definisce la classe

${\mathsf {Set}}_{h}({\mathcal {B}})$

come la classe delle parti della classe ${\mathcal {B}}$ contenente $h$ elementi. Questa classe si può vedere come la classe quoziente espressa da

${\mathsf {Seq}}_{h}({\mathcal {B}})/{\mathfrak {R}}$,

dove ${\mathsf {Seq}}_{h}({\mathcal {B}})$ è l’insieme delle sequenze di lunghezza $h$ le cui componenti appartengono a ${\mathcal {B}}$, e dove la relazione ${\mathfrak {R}}$ mette in equivalenza due ssequenze che coincidono a meno di una permutazione. Si ha

$|{\mathsf {Seq}}_{h}({\mathcal {B}})|=h!|{\mathsf {Set}}_{h}({\mathcal {B}})|$.

La classe delle parti della classe ${\mathcal {B}}$ è definita come

${\mathcal {A}}={\mathsf {Set}}({\mathcal {B}})=\bigcup _{h\geq 0}{\mathsf {Set}}_{h}({\mathcal {B}})$,

e la serie generatrice esponenziale corrispondente è

$A(z)=\sum _{h\geq 0}{\frac {1}{h!}}B(z)^{h}=\exp(1-B(z))$.

Ciclo

Si definisce la classe

${\mathsf {Cyc}}_{h}({\mathcal {B}})$

come la classe dei cicli di lunghezza $h$ i cui componenti sono elementi della classe ${\mathcal {B}}$. Questa si può vedere come il quoziente della classe delle sequenze di lunghezza $h$ di elementi de ${\mathcal {B}}$ rispetto all'insieme delle permutazioni circolari di suoi elementi. Per essa si ottiene

$|{\mathsf {Seq}}_{h}({\mathcal {B}})|=h|{\mathsf {Cyc}}_{h}({\mathcal {B}})|$.

La classe dei cicli della classe ${\mathcal {B}}$ è per definizione

${\mathcal {A}}={\mathsf {Cyc}}({\mathcal {B}})=\bigcup _{h\geq 0}{\mathsf {Cyc}}_{h}({\mathcal {B}})$,

e la serie generatrice esponenziale corrispondente è

$A(z)=\sum _{h\geq 0}{\frac {1}{h}}B(z)^{h}=\log(1-B(z))$.

Due casi particolari sono l'operatore di costruzione dei cicli di lunghezza pari, e quello dei cicli di lunghezza dispari, qui sono definiti rispettivamente

$\bigcup _{h\geq 0}{\mathsf {Cyc}}_{2h}({\mathcal {B}})$ e $\bigcup _{h\geq 0}{\mathsf {Cyc}}_{2h+1}({\mathcal {B}})$.

Le loro rispettive serie generatrici sono

${\frac {1}{2}}\log {\frac {1}{1-B(z)^{2}}}$ e ${\frac {1}{2}}\log {\frac {1+B(z)}{1-B(z)}}$.

Esempi

Permutazioni. Une permutazione può essere vista come un insieme de cicli su supporti disgiunti. Questo conduce all'equazione simbolica

${\mathcal {P}}={\mathsf {Set}}({\mathsf {Cyc}}({\mathcal {Z}}))$,

dove ${\mathcal {Z}}$ è la classe formata da un solo elemento di taglia 1. La serie generatrice esponenziale è

$P(z)=\exp {\bigl (}\log {\bigl (}{\frac {1}{1-z}}{\bigr )}{\bigr )}={\frac {1}{1-z}}$.

Involuzioni. Una involuzione è una permutazione $\sigma$ tale che $\sigma ^{2}=\operatorname {Id}$. Una involuzione si può vedere come un insieme di cicli di lunghezza 1 o 2 sopra supporti disgiunti. L'equazione simbolica è dunque

${\mathcal {I}}={\mathsf {Set}}({\mathsf {Cyc_{1}}}({\mathcal {Z}})+{\mathsf {Cyc_{2}}}({\mathcal {Z}}))$,

e la corrispondente serie generatrice esponenziale è $I(z)=exp(z+z^{2}/2)$. Un calcolo elementare conduce alla seguente espressione chiusa

$[z^{n}]I(z)=\sum _{i=0}^{\lceil n/2\rceil }{\frac {n!}{i!(n-2i)!2^{i}}}$

Dérangements. Un dérangement è una permutazione priva di punti fissi. La sua definizione simbolica è

${\mathcal {D}}={\mathsf {Set}}({\mathsf {Cyc}}_{h\geq 2}({\mathcal {Z}}))$,

e la sua funzione generatrice esponenziale

$D(z)=\exp(z^{2}/2+z^{3}/3+\cdots )=\exp {\bigl (}\log {\bigl (}{\frac {1}{1-z}}{\bigr )}-z{\bigr )}={\frac {e^{-z}}{1-z}}$.

Per valutare il numero $d_{n}$ di dérangements di taglia $n$, basta osservare che $D(z)$ ha la singolarità in $z=1$. Lo sviluppo della $D(z)$ intorno a questo punto è

$D(z)\sim _{z\to 1}{\frac {e^{-1}}{1-z}}$, de sorte $d_{n}=[z^{n}]D(z)\sim {\frac {n!}{e}}$.

Alberi. Un albero con radice è formato da un vertice e da un insieme di sottoalberi; sono interessanti sia alberi etichettati che alberi non etichettati. Per gli alberi etichettati, l'equazione simbolica è

${\mathcal {T}}={\mathcal {Z}}\star {\mathsf {Set}}({\mathcal {T}})$,

e la serie esponenziale correspondante è:

$T(z)=z\exp(T(z))$.

Un albero piano con radice e non etichettato, formato da un vertice e da una sequenza di sottoalberi, come equazione simbolica ha

${\mathcal {T}}={\mathcal {Z}}\times {\mathsf {Seq}}({\mathcal {T}})$,

e come serie generatrice ordinaria

$T(z)={\frac {z}{1-z}}$.

Multi-insiemi

La costruzione della classe dei multiinsiemi, ossia delle parti dotate di molteplicità è simile a quella della classe delle parti. In questa classe

${\mathcal {A}}={\mathsf {MSet}}({\mathcal {B}})$,

ogni elemento di ${\mathcal {B}}$ può figurare in una parte un numero arbitrario di volte. si ottiene quindi

${\mathcal {A}}={\mathsf {MSet}}({\mathcal {B}})=\prod _{b\in {\mathcal {B}}}{\mathsf {Seq}}(\{b\})$.

Denotando con $B_{n}$ il numero di elementi di ${\mathcal {B}}$aventi taglia $n$, si giunge alla relazione

${\begin{aligned}A(z)&{}=\prod _{b\in {\mathcal {B}}}(1-z^{|b|})^{-1}=\prod _{n=1}^{\infty }(1-z^{n})^{-B_{n}}\\&{}=\exp \left(\log \prod _{n=1}^{\infty }(1-z^{n})^{-B_{n}}\right)=\exp \left(\sum _{n=1}^{\infty }-B_{n}\log(1-z^{n})\right)\\&{}=\exp \left(\sum _{k=1}^{\infty }{\frac {B(z^{k})}{k}}\right),\end{aligned}}$

Una applicazione di questi risultati riguarda le partizioni degli interi. Denotando con ${\mathcal {I}}$ la classe degli interi positivi, per la quale come taglia di ogni intero si assume il suo valore, si ha

${\mathcal {I}}={\mathcal {Z}}\times {\mathsf {Seq}}({\mathcal {Z}})$.

La serie generatrice di ${\mathcal {I}}$ è allora

$I(z)={\frac {z}{1-z}}$ .

L'insieme delle partizioni degli interi è la classe dei multiinsiemi degli interi positivi. Se la denotiamo con ${\mathcal {P}}$, si ottiene dunque la formule

${\mathcal {P}}={\mathsf {MSet}}({\mathcal {I}})$ .

La serie generatrice di ${\mathcal {P}}$ è

$P(z)=\exp \left(I(z)+{\frac {1}{2}}I(z^{2})+{\frac {1}{3}}I(z^{3})+\cdots \right)$ .

Di questa serie non si conosce alcuna espressione chiusa, ma si può calcolare il valore asintotico di ciascuno dei suoi coefficienti.

Bibliografia

• (EN) Jérémie Lumbroso, Basile Morcrette: Gentle Introduction to Analytic Combinatorics in CIMPA Summer School Analysis of Random Structures, An Najah University, Nablus, Palestine, 18-27 august 2014 - http://lipn.univ-paris13.fr/~nicodeme/nablus14/nafiles/gentle.pdf
• (EN) Robin Pemantle, Mark C. Wilson (2013): Analytic Combinatorics in Several Variables, Cambridge University Press, ISBN 978-1107031579
• (EN) Herbert Wilf (1990): Generatingfunctionology, Academic Press, 1990, ISBN 0-12-751955-6 - [1]
• (EN) François Bergeron, Gilbert Labelle, Pierre Leroux (1998):Combinatorial Species and Tree-like Structures, Cambridge University Press, ISBN 9780521573238
• (EN) Micha Hofri (1995): Analysis of Algorithms: Computational Methods and Mathematical Tools, Oxford University Press, ISBN 0-19-509954-0.