Combinatoire analytique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, et plus précisément en combinatoire, la combinatoire analytique (en anglais : analytic combinatorics) est un ensemble de techniques décrivant des problèmes combinatoires dans le langage des séries génératrices, et s'appuyant en particulier sur l'analyse complexe pour obtenir des résultats asymptotiques sur les objets combinatoires initiaux.

Les résultats de combinatoire analytique permettent notamment une analyse fine de la complexité de certains algorithmes.

Introduction[modifier | modifier le code]

La combinatoire analytique s'organise autour de plusieurs thèmes : des méthodes symboliques sont employées pour décrire des relations entre des objets mathématiques discrets et des opérations algébriques sur des fonctions génératrices d'énumération ; des méthodes d'analyse complexe sont développées en vue d'extraire des fonctions génératrices des informations sur le comportement asymptotique du nombre d'objets énumérés ; c'est la nature des singularités qui est la clé de l'étude du comportement asymptotique. Enfin, une application importante est l'étude de propriétés probabilistes de grandes structures aléatoires.

Cette théorie a été largement développée notamment par Philippe Flajolet et son école. Elle est détaillée dans son livre avec Robert Sedgewick, Analytic Combinatorics[1]. Des contributions antérieures à cette approche peuvent être trouvées dans des travaux de Leonhard Euler, Arthur Cayley, Srinivasa Ramanujan, George Pólya et Donald Knuth notamment.

Classes combinatoire[modifier | modifier le code]

Les méthodes symboliques s'appuient sur le concept de classe combinatoire, c'est-à-dire d'ensembles d'objets dont chacun a une taille. Les méthodes consistent en une association entre opérations ensemblistes ou algébriques sur les classes opératoires d'une part, et des opérations algébriques sur des séries génératrices d'autre part. Le but est d'obtenir un processus de traduction purement formel. On constate que deux types de fonctions génératrices sont appropriées, les fonctions génératrices ordinaires pour des structures non étiquetées, et des fonctions génératrices exponentielles pour des structures étiquetées.

Définitions[modifier | modifier le code]

Une classe combinatoire est par définition un ensemble \mathcal{A} muni d'une application |\cdot|:\mathcal{A}\to\N appelée taille qui, à chaque élément a de l'ensemble \mathcal{A} associe un entier naturel |a|. On demande de plus que, pour chaque n, le nombre d'éléments de taille n est fini.

Comme la définition le suggère, un même ensemble peut être doté de plusieurs tailles différentes. Ainsi, la taille des arbres binaires peut être leur nombre de sommet; une autre taille est leur hauteur. Mais le nombre de feuilles n'est pas une taille valide, parce qu'il existe une infinité d'arbres binaires « filiformes » (où chaque nœud n'a qu'il seul enfant) qui n'ont qu'une feuille unique. En général, un objet d'une certaine taille est formé de composants élémentaires que l’on appelle parfois des atomes (comme les sommets d'un graphe par exemple).

Soit maintenant \mathcal{A} un ensemble combinatoire, et soit a_n le nombre d'éléments de taille n de \mathcal{A}. La série génératrice ordinaire associée à \mathcal{A} est par définition la série A(z) définie par

A(z)=\sum_{n=0}^\infty a_nz^n.

Il est parfois commode de considérer une autre expression équivalente pour la série, à savoir :

A(z)=\sum_{a\in \mathcal{A}} z^{|a|}..

On considère aussi, dans le cas de structures étiquetées, des séries génératrices exponentielles dont il sera question plus bas.

En général, les séries génératrices associées au dénombrement d'objets combinatoires sont des séries formelles, que l'on manipule sans considération de convergence. Dans le cadre de la combinatoire analytique, on étudie leur comportement dans le cadre de l’analyse complexe. L'observation fondamentale utilisée - qui est explicitée plus loin - est que la nature de la singularité sur l'axe réel positif donne des informations précises sur la croissance des nombres a_n d'objets de taille n.

Une notation utile pour l'extraction de coefficients d'une série génératrice f(z) est la suivante : on désigne par [z^n] le coefficient de la variable z^n, de sorte que, pour

f(z)=\sum_{n=0}^\infty f_nz^n,

on a :

[z^n]f(z)=f_n.

Exemples[modifier | modifier le code]

Quelques exemples usuels sont les suivants :

  • Classe des mots sur un alphabet binaire, la taille est la longueur du mot. Il y a 2^n mots de longueur n. La série génératrice est :
\frac1{1-2z}
  • Compositions d'entiers (une composition d'un entier positif n est une suite (p_1,p_2,\ldots, p_r) d'entiers positifs tels que p_1+p_2+\cdots+p_r=n). Chaque entier positif n possède 2^{n-1} compositions. La série génératrice est :
\frac{z}{1-2z}
  • Arbres binaires complets. Le nombre d'arbres binaires complets à n nœuds internes est
\frac1{n+1}\binom {2n} n,
et la série génératrice est :
\frac{1-\sqrt{1-4z}}{2z}.

La méthode symbolique[modifier | modifier le code]

La méthode symbolique est un procédé qui permet de traduire directement des relations entre classes combinatoires dans les séries génératrices correspondantes. L'algorithme consiste à commencer avec des classes combinatoires très simples, et à les composer à l'aide d'opérateurs au comportement connu. Ces opérateurs ensemblistes comprennent diverses opérations simples, comme la réunion disjointe, le produit cartésien; d'autres opérations, comme l'ensemble des parties, la formation de suites, de multiensembles sont un peu plus complexes. Enfin des définitions recursives sont possibles. L'attrait de la méthode est que la définition ensembliste, ou symbolique, se traduite directement en de relations algébriques sur les fonctions génératrices.

Deux types de séries génératrices sont utilisées usuellement en combinatoire, les séries génératrices ordinaires, pour des classes combinatoires d'objets non étiquetés, et des séries génératrices exponentielles, pour des classes combinatoires d'objets étiquetés,

Il est d'usage, dans cette théorie, de noter les classe combinatoires par des lettres cursives, et leurs séries génératrices par les même lettres, droites. Ainsi, les séries associées à des classes combinatoires \mathcal{A}, \mathcal{B} ou \mathcal{C} sont notées respectivement A(z), B(z) et C(z).

Constructions élémentaires[modifier | modifier le code]

Les briques de base sont des classes formées d'un seul objet. Deux types de classes sont utiles : celles où le singleton est de taille nulle, et celles dont le singleton est de taille un. Une classe \mathcal{E}=\{\varepsilon\} du premier type a donc un élément \varepsilon de taille nulle, et sa série génératrice est la fonction constante E(z)=1. Une classe \mathcal{Z}=\{z\} du deuxième type au un seul élément, de taille un, et sa série génératrice est Z(z)=z. Les opérations élémentaires sont l'union disjointe, le produit cartésien , la formation de suites.

Union disjointe[modifier | modifier le code]

On écrit \mathcal{A}= \mathcal{B}+\mathcal{C} si la classe \mathcal{A} est l’union disjointe des classes \mathcal{B} et \mathcal{C}. Cette relation se traduit en séries génératrices par

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

puisque en effet

A(z)=\sum_{a\in\mathcal{A}}z^{|a|}=\sum_{a\in\mathcal{B}}z^{|a|}+\sum_{a\in\mathcal{C}}z^{|a|}=B(z)+C(z).

Produit cartésien[modifier | modifier le code]

On écrit \mathcal{A}= \mathcal{B}\times\mathcal{C} si la classe \mathcal{A} est l'ensemble des couples a=(b,c), avec b\in\mathcal{B} et c\in\mathcal{C}. La fonction taille est définie par |a|=|b|+|c|. On a alors, pour les séries génératrices, la relation

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

Séquences[modifier | modifier le code]

On écrit \mathcal{A}= \mathsf{Seq}(\mathcal{B}) lorsque \mathcal{A} est l'ensemble des suites finies d éléments de \mathcal{B}. En d'autres termes,

\mathcal{A}=\mathcal{E}+\mathcal{B}+\mathcal{B}\times\mathcal{B}+\mathcal{B}\times\mathcal{B}\times\mathcal{B}+\cdots , ou encore \mathcal{A}=\{(b_1,\ldots,b_h)\mid h\ge0, b_j\in\mathcal{B}\} .

La taille d'une suite (b_1,\ldots,b_h) est la somme des tailles de ses composants. Pour que l’opération soit bien définie, la classe \mathcal{B} ne doit pas contenir d'étélemnt de taille 0 car sinon la classe \mathcal{A} contiendrait une infinité d'éléments d'une taille donnée. La traduction en séries génératrices est

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

La série A(z) est appelée parfois la quasi-inverse de la série B(z).

Définition récursive[modifier | modifier le code]

Lorsque certaines conditions assez techniques sont remplies[2], on peut définir une classe combinatoire de façon récursive. Voici des exemples.

Arbres binaires[modifier | modifier le code]

Le premier exemple est celui des arbres binaire. Un arbre binaire est soit l’arbre binaire vide, soit formé d'une racine et de deux sous-arbres qui sont des arbres binaires. L'équation de la classe combinatoire \mathcal{B} des arbres binaires est donc :

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

\mathcal{E} est réduite à un élément de taille 0 et \mathcal{Z} est composé d'un élément de taille 1. Cette équation se traduit en l’équation

B(z)=1+zB(z)^2.

Arbres unaires-binaires[modifier | modifier le code]

Un arbre unaire-binaire est un arbre où chaque nœud interne a un ou deux enfants. L'équation symbolique s'écrit

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

d'où l'on déduit l'équation fonctionnelle

U(z)=z +zU(z)+zU(z)^2..

Exemples[modifier | modifier le code]

On peut employer la méthode symbolique même dans des cas très élémentaires :

Mots binaires[modifier | modifier le code]

Un mot binaire est une suite de symboles 0 et 1. On a deux classes combinatoires \mathcal{Z}_0=\{0\} et \mathcal{Z}_1=\{1\} dont la série génératrice est z. Les mots binaires sont donnés par la construction

\mathcal{W}_0=\mathsf{Seq}(\mathcal{Z}_0+\mathcal{Z}_1),

leur série génératrice est

W(z)=\frac1{1-(z+z)} et [z^n]W(z)=2^n.

C'est utiliser une grosse artillerie pour un exemple tout simple.

Composition restreinte d'entiers[modifier | modifier le code]

Le problème est de couvrir le segment [0,n] avec des briques de taille 1 et 2, en d'autre termes d'écrire l'entier n comme une somme dont les termes sont 1 ou 2, et de compter le nombre de façons de le faire. Par exemple, l'entier 4 possède les cinq écritures :

4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2 .

Il est facile de voir directement que le nombre de ces compositions de n est F_n, le ne nombre de Fibonacci. Pour utiliser la méthode symbolique, on considère deux classes \mathcal{Z}_1 et \mathcal{Z}_2 composées d'un élément unique de taille 1 et de taille 2 respectivement. Alors la classe de couvertures est

\mathcal{F}=\mathsf{Seq}(\mathcal{Z}_1+\mathcal{Z}_2)

et la série génératrice est :

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

Autres constructions symboliques[modifier | modifier le code]

D'autre constructions syboliques importantes sont : Cycles. Les cycles \mathcal{A} = \mathsf{Cyc}(\mathcal{B}) sont comme des séquences, sauf que deux objets qui s'obtiennent l'un de l'autre par une rotation circulaire ne sont pas considérés comme distincts. La série génératrice est nettement plus compliquée; dans le cas étiqueté, elle est plus simple. Ici, elle s'écrit

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

\phi(k)\, est l'indicatrice d'Euler. Classe pointée. La classe \Theta\mathcal{B} est formée d'objets de \mathcal{B} qui sont « pointés » : dans chaque objet, un atome est distingué. Par exemple, les arbres enracinés sont des arbres libres pointés. Formellement, chaque objet est augmenté d'un élément de taille zéro sur un de ses atomes. La série génératrice est

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

Substitution. La classe \mathcal{B} \circ \mathcal{C} est obtenue en substituant, à chaque atome d'un élément de \mathcal{B}, un élément de la classe \mathcal{C}. La série génératrice est simplement B(C(z)).

Analyse[modifier | modifier le code]

Les méthodes d'analyse complexe se concentrent autour du processus d'extraction d'informations asymptotiques à partir de fonctions génératrices. Il existe un ensemble de résultats qui fournissent une traduction systématique entre fonctions génératrices et la forme asymptotique des coefficients.

Dans la plupart des situations qui se présentent en combinatoire, une série formelle

f(z)=\sum_{n\ge0}f_nz^n

de dénombrement peut être vue comme le développement, autour de 0, d'une fonction analytique f(z). Le rayon de convergence R de la série est donné par exemple par

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

Ceci signifie que

f_n\sim R^{-n}\theta(n)

\theta(n) est une fonction sous-exponentielle de n. Il y a donc une singularité sur le rayon de convergence, et un théorème classique de Pringsheim (na pas confondre avec un théorème de Pringsheim de même nom) dit que si les coefficients f_n sont non négatifs, ce qui est bien le cas dans des séries énumératrices, alors il existe une singularité réelle positive au point z=R.

Cas des séries rationnelles[modifier | modifier le code]

Avec les constructeurs autres que la récursivité, c'est-à-dire avec \mathcal{E},\mathcal{Z} et les opérateurs +, \times, \mathsf{Seq}, on obtient que des séries rationnelles. Dans ce cas, le terme f_n est asymptotiquement équivalent à une somme de termes de la forme c n^kR^{-n}. Plus précisément, si la singularité dominante est de multiplicité k, alors

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

Exemple.- On considère la série rationnelle

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

Ses singularités sont \sqrt2, -\sqrt2,1,1/2,\phi, \bar\phi (\phi est le nombre d'or). La singularité dominante est 1/2, et sa multiplicité est 5. On a donc

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

Un cas plus général[modifier | modifier le code]

Le cas général est plus délicat. La démarche adoptée est la suivante : on considère une famille générale mais bien précise de fonctions (combinaisons de puissance (complexes) de (1-z) et de \log(1-z)) pour lesquelles on sait obtenir des estimations asymptotiques à l'aide d'outils d'analyse complexe plus ou moins complexe. Ensuite, on emploie un autre principe de base, appelé le théorème de transfert, qui dit que si deux fonctions sont « voisines » autour de leur singularité réelle, il en est de même de leurs coefficients. Le résultat sur la famille de fonctions est le suivant[3], exprimé ici dans le cas où la singularité est 1; on peut toujours s'y ramener par un changement de variable.

Soient \alpha\in\R\setminus\{0,-1,-2,\ldots\} et k\in\N. On a
[z^n]\frac1{1-z)^\alpha}\log^k\left(\frac1{1-z}\right)\sim \frac{n^{\alpha-2}}{\Gamma(\alpha)}\log^k(n),
\Gamma est la fonction Gamma usuelle.

De nombreux exemples sont donnés dans le livre de Flajolet et Sedgewick[4]. En voici quelques-uns :

Fonction Coefficients
(1-z)^{3/2} \frac1{\sqrt{\pi n^5}}\bigl(\frac34 + \frac{45}{32n}+\frac{1155}{512n^2}+ O\bigl(\frac1{n^3}\bigr)\bigr)
(1-z)^{1/2} -\frac1{\sqrt{\pi n^3}}\bigl(\frac12 + \frac3{16n}+\frac{25}{256n^2}+ O(\frac1{n^3})\bigr)
(1-z)^{1/2}\log(1-z) -\frac1{\sqrt{\pi n^3}}\bigl(\frac12\log n + \frac{\gamma +2\log2-2}2+O\bigl(\frac{\log n}n\bigr)\bigr)
(1-z)^{-1/2} \frac1{\sqrt{\pi n}}\bigl(1-\frac1{8n} + \frac1{128n^2}+\frac5{1024n^3}+O\bigl(\frac1{n^4}\bigr)\bigr)
(1-z)^{-1/3} \frac1{\Gamma(1/3)n^{2/3}}\bigl(1+O\bigl(\frac1n\bigr)\bigr)
(1-z)^{-1}\log^2(1-z) \log^2n+2\gamma\log n+\gamma^2-\frac{\pi^2}6+O\bigl(\frac{\log n}n\bigr)

Le théorème de transfert[modifier | modifier le code]

Le théorème de transfert[5] énonce qu'il suffit de connaître le comportement de deux fonctions autour de leur plus petite singularité pour pouvoir comparer le comportement asymptotique de leurs coefficients. L'énoncé est le suivant.

Soient f(z) et g(z) deux fonctions dont la plus petite singularité est 1. Alors — Si f(z)\sim_{z\to1}g(z), alors f_n\sim g_n.
— Si f(z)=_{z\to1}O(g(z)), alors f_n=O(g_n).
— Si f(z)=_{z\to1}o(g(z)), alors f_n=o(g_n).

Une exemple[modifier | modifier le code]

On retrouve comme suit l'évaluation asymptotique du nombre d'arbres binaires. On part de l'équation symbolique

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

\mathcal{E} est réduite à un élément de taille 0 et \mathcal{Z} est composé d'un élément de taille 1. Cette équation se traduit en l’équation

B(z)=1+zB(z)^2.

On résout l'équation et on trouve

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

La fonction a une singularité en z=1/4, et son ordre est -1/2. Autour de z=1/4, on peut écrire

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

et par le théorème général on obtient

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

parce que \Gamma(-1/2)=-2\sqrt\pi.

Classes combinatoires étiquetées[modifier | modifier le code]

Une classe combinatoire est étiquetée si ses éléments sont étiquetés. Par définition, un tel objet combinatoire, de taille n, est de plus doté d'une permutation de \{1,\ldots,n\}. Les exemples les plus pertinents d'objets étiquetés sont les graphes.

Pour énumérer les objets d'une classe étiquetée, on emploie des séries génératrices exponentielles, où les coefficients sont normalisées par une factorielle.

Définition[modifier | modifier le code]

Plus formellement, soit \mathcal{A} une classe combinatoire étiquetée, et soit a_n, pour n\ge0, le nombre d'objets de taille n dans cette classe. La série génératrice exponentielle associée à \mathcal{A} est

A(z)=\sum_{n=0}^\infty a_n\frac{z^n}{n!}.

Il est équivalent d'écrire

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

L'extraction d'un coefficient de cette série donne

[z^n]A(z)=\frac{a_n}{n!}, donc a_n=n![z^n]A(z).

Exemples[modifier | modifier le code]

Permutations. Soit \mathcal{P} la classe des permutations. Sa série génératrice exponentielle est

P(z)=\sum_{n\ge0}n!\frac{z^n}{n!}=\frac1{1-z}.

Graphes sans arête. Il existe, pour chaque entier n, un seul graphe sans arête. La série génératrice correspondante est

\sum_{n\ge0} \frac{z^n}{n!} = e^z

La même série compte les graphes complets.

Graphes cycliques. Le nombre de graphes étiquetés de n sommets formés d'un seul cycle est (n-1)!. Leur série génératrice exponentielle est donc

\sum_{n\ge0}(n-1)! \frac{z^n}{n!} =\sum_{n\ge0}\frac{z^n}{n}=\log\bigl(\frac1{1-z}\bigr).

Constructions[modifier | modifier le code]

Produit[modifier | modifier le code]

La construction d'une somme disjointe de classes combinatoires se transpose sans modifications aux classes étiquetées. Pour le produit, il faut être plus attentif. Soient \mathcal{B} et \mathcal{C} deux classes combinatoires étiquetées. Le produit cartésien est formé de couples (b,c) d'objets étiquetées, mais un tel couple n’est pas correctement étiqueté puisque ses éléments n'ont pas des étiquettes distinctes. On définit une structure (b',c') associée, dont les éléments ont exactement les étiquettes \{1,\ldots,|b|+|c|\}, et où l'ordre relatif des étiquettes de chaque élément est respecté. On définit

b\star c

comme l'ensemble des couples (b',c') ainsi ré-étiquetés. La famille b\star c contient exactement \binom{|b|+|c|}{|b|} éléments. Le produite étiqueté des classes \mathcal{B} et \mathcal{C} est par définition

\mathcal{A}=\mathcal{B}\star \mathcal{C}=\bigcup_{b\in\mathcal{B},c\in\mathcal{C}}b\star c.

Pour les séries génératrices exponentielles, on a

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

En effet, pour b\in\mathcal{B} et c\in\mathcal{C}, on a

\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 donc

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(zC(z).

Séquence[modifier | modifier le code]

À partir de la somme disjointe et du produit, on construit l'opérateur de séquence comme dans le cas ordinaire : On écrit \mathcal{A}= \mathsf{Seq}(\mathcal{B}) lorsque \mathcal{A} est l'ensemble des suites finies d'éléments de \mathcal{B}; ici \mathcal{B} n'a pas d'élément de taille nulle. En d'autres termes,

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

ou encore \mathcal{A}=\{(b_1,\ldots,b_h)\mid h\ge0, b_j\in\mathcal{B}\} , où les suites son ré-étiquetées. La série génératrices exponentielle est

A(z)=\sum_{h\ge0}B(z)^h=\frac1{1-B(z)}.

Ensemble des parties[modifier | modifier le code]

Les définitions d'ensemble et de cycle donnée ici s'appliquent aussi bien aux structures non étiquetées. On définit la classe

\mathsf{Set}_h(\mathcal{B})

comme la classe des parties de la classe \mathcal{B} contenant h éléments. On peut voir cette classe comme la classe quotient de

\mathsf{Seq}_h(\mathcal{B})/\mathfrak{R} ,

\mathsf{Seq}_h(\mathcal{B}) est l’ensemble des suites à h éléments de \mathcal{B}, et où \mathfrak{R} met en équivalence deux suites qui sont les mêmes à une permutation de ses éléments près. On a

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

La classe des parties de la classe \mathcal{B} est par définition

\mathcal{A}=\mathsf{Set}(\mathcal{B})=\bigcup_{h\ge0} \mathsf{Set}_h(\mathcal{B}),

et la série génératrice exponentielle correspondante est

A(z)=\sum_{h\ge0}\frac1{h!}B(z)^h=\exp(1-B(z)).

Cycle[modifier | modifier le code]

On définit la classe

\mathsf{Cyc}_h(\mathcal{B})

comme la classe des cycles de h éléments de la classe \mathcal{B}. On peut la voir comme le quotient de la classe des suites de longueur h d'éléments de \mathcal{B} par l'ensemble des permutations circulaires de ses éléments. On a

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

La classe des cycles de la classe \mathcal{B} est par définition

\mathcal{A}=\mathsf{Cyc}(\mathcal{B})=\bigcup_{h\ge0} \mathsf{Cyc}_h(\mathcal{B}),

et la série génératrice exponentielle correspondante est

A(z)=\sum_{h\ge0}\frac1h B(z)^h=\log(1-B(z)).

Deux cas particuliers sont l'opérateur de construction des cycles de longueur paire, et celui de longueur impaire, qui sont respectivement

\bigcup_{h\ge0} \mathsf{Cyc}_{2h}(\mathcal{B}) et \bigcup_{h\ge0} \mathsf{Cyc}_{2h+1}(\mathcal{B}).

Leurs séries génératrices sont respectivement

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

Exemples[modifier | modifier le code]

Permutations. Une permutation peut être vue comme un ensemble de cycles de supports disjoints. Ceci conduit à l'équation symbolique

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

\mathcal{Z} est la classe formée d'un seul élément de taille 1. La série génératrice exponentielle est

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

Involutions. Une involution est une permutation \sigma telle que \sigma^2=\operatorname{Id}. On peut voir une involution comme un ensemble de cycles de longueur 1 ou 2 à supports disjoints. L'équation symbolique est donc

\mathcal{I}=\mathsf{Set}(\mathsf{Cyc_1}(\mathcal{Z})+\mathsf{Cyc_2}(\mathcal{Z})),

et a série génératrice exponentielle est I(z)=exp(z+z^2/2). Un calcul élémentaire permet d'obtenir l'expression close

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

Dérangements. Un dérangement est une permutation sans point fix. La définition symbolique est

\mathcal{D}=\mathsf{Set}(\mathsf{Cyc}_{h\ge2}(\mathcal{Z})),

et la fonction génératrice exponentielle est

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

Pour évaluer le nombre d_n de dérangements de taille n, on observe que la singularité de D(z) est en z=1. Autour de ce point, le développement de D(z) est

D(z)\sim_{z\to1}\frac{e^{-1}}{1-z}, de sorte d_n=[z^n]D(z)\sim\frac{n!}e.

Arbres. Un arbre enraciné est formé d'un sommet et d'un ensemble de sous-arbres. Ce sont des structures étiquetées ou non. Pour les arbres étiquetés, l'équation symbolique est

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

et la série exponentielle correspondante est :

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

Pour un arbre plane enraciné et non étiqueté, formé d'un sommet et d'une suite de sous-arbres, l'équation symbolique est

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

et la série génératrice ordinaire est :

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

Multi-ensemble[modifier | modifier le code]

La construction de la classe des multi-ensembles ou parties avec multiplicité est semblable à celle des parties. Dans la classe

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

chaque élément de \mathcal{B} peut figurer un nombre arbitraire de fois dans une parties. On obtient :

\mathcal{A}=\mathsf{MSet}(\mathcal{B}) = \prod_{b \in \mathcal{B}} \mathsf{Seq}(\{b\}).

Ceci conduit à la relation (ici B_n est le nombre d'éléments de taille n de \mathcal{B}) :

\begin{align} 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{align}

Un exemple d'application est constitué des partitions d'entiers. On définit d'abord la classe des entiers positifs, notée ici \mathcal{I}, où la taille de chaque entier est sa valeur

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

La série génératrice de\mathcal{I} iest alors

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

L'ensemble des partitions d'entiers est la classe des multi-ensembles d'entiers positifs. Si on la note \mathcal{P}, on obtient donc la formule

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

La série génératrice de \mathcal{P} est

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

Il n'y a pas de formule close connue pour cette série, mais on peut calculer la valeur asymptotique de ses coefficients.

Notes et références[modifier | modifier le code]

  1. Flajolet et Sedgewick 2008.
  2. Flajolet et Sedgewick 2008, Chap I, §2.3..
  3. Flajolet et Sedgewick 2008, Theorem VI.2, p. 385.
  4. Flajolet et Sedgewick 2008, Figure VI.5, p. 388.
  5. Flajolet et Sedgewick 2009, Transfert Lemma, Th. VI.3, p. 390.

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Analytic Combinatorics » (voir la liste des auteurs)

Bibliographie[modifier | modifier le code]

  • (en) Herbert Wilf, Generatingfunctionology, Academic Press, 1990, ISBN 0-12-751955-6. (lire en ligne)
  • Jérémie Lumbroso et Basile Morcrette, « A Gentle Introduction to Analytic Combinatorics », dans CIMPA Summer School Analysis of Random Structures, An Najah University, Naplouse, Palestine,‎ 18-27 août 2014 (lire en ligne) Document utilisé pour la rédaction de l’article
  • François Bergeron, Gilbert Labelle et Pierre Leroux, Combinatorial Species and Tree-like Structures, Cambridge University Press, coll. « Encyclopedia of Mathematics and its Applications » (no 67),‎ 1998, 457 p. (ISBN 9780521573238) — Version française : Théorie des espèces et combinatoire des structures arborescentes, LaCIM, Montréal (1994).
  • (en) Philippe Flajolet et Robert Sedgewick, Analytic Combinatorics, Cambridge University Press,‎ 2008 (ISBN 0-521-89806-4, lire en ligne)
  • Micha Hofri, Analysis of Algorithms: Computational Methods and Mathematical Tools, Oxford University Press (1995).
  • Robin Pemantle et Mark C. Wilson, Analytic Combinatorics in Several Variables, Cambridge University Press, coll. « Cambridge Studies in Advanced Mathematics » (no 140),‎ 2013, 392 p. (ISBN 978-1107031579).