Combinatoire analytique

En mathématiques, et plus précisément en combinatoire, la combinatoire analytique (en 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. 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. 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.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (9)

Cours associés (2)

Séances de cours associées (11)

Stirling numbers of the second kind

In mathematics, particularly in combinatorics, a Stirling number of the second kind (or Stirling partition number) is the number of ways to partition a set of n objects into k non-empty subsets and is denoted by or . Stirling numbers of the second kind occur in the field of mathematics called combinatorics and the study of partitions. They are named after James Stirling. The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices.

Stirling numbers of the first kind

In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles (counting fixed points as cycles of length one). The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices. This article is devoted to specifics of Stirling numbers of the first kind.

Combinatoire analytique

MATH-260(a): Discrete mathematics

Study of structures and concepts that do not require the notion of continuity. Graph theory, or study of general countable sets are some of the areas that are covered by discrete mathematics. Emphasis

MATH-260(b): Discrete mathematics

Applications de la théorie ergonomique à la combinatoire

Explore les applications de la théorie ergonomique à la combinatoire et la théorie des nombres, y compris le théorème de Szemerédi et le théorème d'Erdős-Kac.

Pratiques alchimiques et cahiers de laboratoire HUM-402: Experimental history of science I

Plonge dans l'importance historique des pratiques alchimiques, des livres de recettes et des cahiers de laboratoire en tant que formes de transmission des connaissances.

Propriétés ergonomiques de systèmes symboliques de faible complexité

Explore l'influence de la complexité sur les propriétés ergonomiques des systèmes symboliques, présentant le théorème Curtis-Hedlund-Lyndon et les constructions de sous-postes minimaux.