En mathématiques, et plus précisément en combinatoire, la combinatoire analytique (en ) 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
La combinatoire analytique repose fondamentalement sur deux approches : la première approche, combinatoire, également parfois qualifiée de méthode symbolique, permet de décrire des relations entre des objets mathématiques discrets en les transcrivant directement en termes d'opérations algébriques sur les séries génératrices associées; la deuxième approche, analytique, utilise ou développe des outils danalyse complexe en vue d'extraire de ces séries génératrices des informations sur le comportement asymptotique du nombre d'objets énumérés. C'est ainsi la nature des singularités de ces séries qui est la clé de l'étude du comportement asymptotique des objets discrets initiaux. 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.. Elle trouve sa source dans des travaux de précurseurs comme Leonhard Euler, Arthur Cayley, Srinivasa Ramanujan, Gaston Darboux, George Pólya et Donald Knuth.
Classes combinatoire
La méthode symbolique s'appuie sur le concept de classe combinatoire, c'est-à-dire d'ensembles d'objets, où chaque objet a une taille. La méthode permet de traduire des opérations ensemblistes sur les classes en des opérations algébriques sur les séries génératrices associées. On obtient ainsi un processus de traduction purement formel, et automatisable. En pratique, on utilise souvent des séries génératrices dites ordinaires pour les structures non étiquetées, et des séries génératrices exponentielles pour les structures étiquetées. D'autres types de séries génératrices (de Dirichlet, de Poisson, de Bell, de Lambert, de Wright, ...) sont toutefois aussi utilisables.
Définitions
Une classe combinatoire est par définition un ensemble muni d'une application appelée taille qui, à chaque élément de l'ensemble associe un entier naturel . On demande de plus que, pour chaque , le nombre d'éléments de taille 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 un ensemble combinatoire, et soit le nombre d'éléments de taille de . La série génératrice ordinaire associée à est par définition la série définie par . Il est parfois commode de considérer une autre expression équivalente pour la série, à savoir : .
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 peut manipuler sans considération de convergence (au sens de convergence dans les réels ou dans les complexes), mais il existe en fait une notion de convergence dans l'anneau des séries formels qui repose sur la valuation des séries et qui donne un cadre rigoureux à toutes les manipulations mentionnées ci-après. Dans le cadre de la combinatoire analytique, les questions de convergence jouent d'ailleurs un rôle, puisqu'on étudie le comportement des séries en des points précis, 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 d'objets de taille .
Une notation utile pour l'extraction de coefficients d'une série génératrice est la suivante : on désigne par le coefficient de la variable , de sorte que, pour , on a : . Dans la suite de cet article, on parle parfois, avec un léger abus de langage, des coefficients d'une fonction, pour désigner les coefficients du développement de Taylor en 0 de cette fonction.
Exemples Quelques exemples usuels sont les suivants. Classe des mots sur un alphabet binaire, la taille est la longueur du mot. Il y a mots de longueur . La série génératrice est . Compositions d'entiers (une composition d'un entier positif est une suite d'entiers positifs tels que ). Chaque entier positif possède compositions. La série génératrice est . Arbres binaires complets. Le nombre d'arbres binaires complets à nœuds internes est , et la série génératrice est .
Méthode symbolique 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 récursives sont possibles. L'attrait de la méthode est que la définition ensembliste, ou symbolique, se traduit 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 classes combinatoires par des lettres cursives, et leurs séries génératrices par les mêmes lettres, droites. Ainsi, les séries associées à des classes combinatoires ou sont notées respectivement et .
Constructions élémentaires 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 du premier type a donc un élément de taille nulle, et sa série génératrice est la fonction constante . Une classe du deuxième type a un seul élément, de taille un, et sa série génératrice est ainsi . Les opérations élémentaires sont l'union disjointe, le produit cartésien, la formation de suites.
Union disjointe On écrit si la classe est l’union disjointe des classes et . Cette relation se traduit en séries génératrices par
puisqu'en effet .
Produit cartésien On écrit si la classe est l'ensemble des couples , avec et . La fonction taille est définie par . On a alors, pour les séries génératrices, la relation .
Séquences On écrit lorsque est l'ensemble des suites finies d'éléments de . Cette construction est aussi appelée étoile de Kleene en théorie des langages. On peut l'écrire plus formellement comme , ou encore . La taille d'une suite est la somme des tailles de ses composants. Pour que l’opération soit bien définie, la classe ne doit pas contenir d'élément de taille 0 car sinon la classe contiendrait une infinité d'éléments d'une taille donnée. La traduction en séries génératrices est . La série est appelée parfois le quasi-inverse de la série .
Définition récursive Lorsque certaines conditions assez techniques sont remplies., on peut définir une classe combinatoire de façon récursive. Voici des exemples.
Arbres binaires Le premier exemple est celui des arbres binaires. 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 des arbres binaires est donc : , où est réduite à un élément de taille 0 et est composé d'un élément de taille 1. Cette équation se traduit en l’équation .
Arbres unaires-binaires Un arbre unaire-binaire est un arbre où chaque nœud interne a un ou deux enfants qui sont des arbres unaires-binaires. Un arbre composé d'un seul nœud interne (racine) est aussi un arbre unaire-binaire. L'équation symbolique s'écrit
d'où l'on déduit l'équation fonctionnelle .
Exemples On peut employer la méthode symbolique même dans des cas très élémentaires : Mots binaires Un mot binaire est une suite de symboles 0 et 1. On a deux classes combinatoires et dont la série génératrice est . Les mots binaires sont donnés par la construction , leur série génératrice est et . C'est utiliser une grosse artillerie pour un exemple tout simple. Composition restreinte d'entiers Le problème est de couvrir le segment avec des briques de taille 1 et 2, en d'autres termes d'écrire l'entier 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 est , le nombre de Fibonacci. Pour utiliser la méthode symbolique, on considère deux classes et composées d'un élément unique de taille 1 et de taille 2 respectivement. Alors la classe de couvertures est
et la série génératrice est : .
Autres constructions symboliques D'autres constructions symboliques importantes sont : Cycles. Les cycles sont comme des séquences, sauf que deux objets qui s'obtiennent l'un de l'autre par une rotation 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
où est l'indicatrice d'Euler. Classe pointée. La classe est formée d'objets de 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 . Substitution. La classe est obtenue en substituant, à chaque atome d'un élément de , un élément de la classe . La série génératrice est simplement .
Analyse
Les méthodes danalyse 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
de dénombrement peut être vue comme le développement, autour de 0, d'une fonction analytique . Le rayon de convergence de la série est donné par exemple par . Ceci signifie que ) où est une fonction sous-exponentielle de . Il y a donc au moins une singularité sur le bord du disque de convergence, et un théorème classique de Pringsheim dit que si les coefficients sont positifs, ce qui est bien le cas dans des séries énumératrices, alors il existe une singularité réelle positive au point .
Cas des séries rationnelles Pour les séries rationnelles, une décomposition en éléments simples donne une forme close pour le terme , qui s'écrit donc comme une somme de termes de la forme . Ainsi, si la singularité dominante R est de multiplicité , alors .
Exemple. On considère la série rationnelle . Ses singularités sont (où désigne le nombre d'or). La singularité dominante est 1/2, et sa multiplicité est 5. On a donc .
Cas des séries algébrico-logarithmiques