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.

Historique[modifier | modifier le code]

Séries génératrices[modifier | modifier le code]

Article détaillé : série génératrice.

Les séries génératrices sont de deux types : ordinaires (pour compter les objets avec ordre) et exponentielles (pour compter les objets sans ordre).

Une utilisation classique de la combinatoire analytique consiste à établir le comportement asymptotique des coefficients de la série génératrice (qui comptent le nombre d'objets combinatoires de la classe avec une certaine valeur d'un paramètre, comme par exemple le nombre d'objets d'une certaine taille). Le comportement asymptotique dépend de la localisation des singularités de la série génératrice.

Bibliographie[modifier | modifier le code]

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