Combinatoire - Combinatorics

La combinatoire est un domaine des mathématiques principalement concerné par le comptage, à la fois comme moyen et comme fin pour obtenir des résultats, et certaines propriétés des structures finies . Il est étroitement lié à de nombreux autres domaines des mathématiques et a de nombreuses applications allant de la logique à la physique statistique , de la biologie évolutive à l' informatique , etc.

La portée complète de la combinatoire n'est pas universellement acceptée. Selon HJ Ryser , une définition du sujet est difficile car elle traverse tant de subdivisions mathématiques. Dans la mesure où un domaine peut être décrit par les types de problèmes qu'il traite, la combinatoire s'occupe de :

  • l' énumération (comptage) de structures spécifiées, parfois appelées arrangements ou configurations dans un sens très général, associées à des systèmes finis,
  • l' existence de telles structures qui satisfont à certains critères donnés,
  • la construction de ces structures, peut-être de plusieurs manières, et
  • optimisation : trouver la « meilleure » structure ou solution parmi plusieurs possibilités, que ce soit la « plus grande », la « plus petite » ou satisfaisant à un autre critère d'optimalité .

Leon Mirsky a dit : « La combinatoire est une gamme d'études liées qui ont quelque chose en commun et pourtant divergent largement dans leurs objectifs, leurs méthodes et le degré de cohérence qu'elles ont atteint. Une façon de définir la combinatoire est peut-être de décrire ses subdivisions avec leurs problèmes et leurs techniques. C'est l'approche qui est utilisée ci-dessous. Cependant, il existe également des raisons purement historiques pour inclure ou non certains sujets sous l'égide de la combinatoire. Bien que principalement concernées par les systèmes finis, certaines questions et techniques combinatoires peuvent être étendues à un cadre infini (spécifiquement dénombrable ) mais discret .

La combinatoire est bien connue pour l'étendue des problèmes qu'elle aborde. Des problèmes combinatoires surviennent dans de nombreux domaines des mathématiques pures , notamment en algèbre , théorie des probabilités , topologie et géométrie , ainsi que dans ses nombreux domaines d'application. De nombreuses questions combinatoires ont historiquement été considérées isolément, donnant une solution ad hoc à un problème survenant dans un contexte mathématique. À la fin du vingtième siècle, cependant, des méthodes théoriques puissantes et générales ont été développées, faisant de la combinatoire une branche indépendante des mathématiques à part entière. L'une des parties les plus anciennes et les plus accessibles de la combinatoire est la théorie des graphes , qui en elle-même a de nombreux liens naturels avec d'autres domaines. La combinatoire est fréquemment utilisée en informatique pour obtenir des formules et des estimations dans l' analyse d'algorithmes .

Un mathématicien qui étudie la combinatoire s'appelle un combinatoire .

Histoire

Un exemple de sonnerie de changement (avec six cloches), l'un des premiers résultats non triviaux de la théorie des graphes .

Des concepts combinatoires de base et des résultats énumératifs sont apparus dans tout le monde antique . Au 6ème siècle avant notre ère, l' ancien médecin indien Sushruta affirme dans Sushruta Samhita que 63 combinaisons peuvent être faites à partir de 6 goûts différents, pris un à la fois, deux à la fois, etc., calculant ainsi toutes les 2 6  − 1 possibilités. L' historien grec Plutarque discute d'un argument entre Chrysippe (3ème siècle avant notre ère) et Hipparque (2ème siècle avant notre ère) d'un problème énumératif assez délicat, qui s'est avéré plus tard être lié aux nombres de Schröder-Hipparque . Plus tôt, dans l' Ostomachion , Archimède (IIIe siècle avant notre ère) a peut-être considéré le nombre de configurations d'un puzzle de carrelage , tandis que des intérêts combinatoires étaient peut-être présents dans les œuvres perdues d' Apollonius .

Au Moyen Âge , la combinatoire continua à être étudiée, largement en dehors de la civilisation européenne . Le mathématicien indien Mahāvīra (vers 850) a fourni des formules pour le nombre de permutations et de combinaisons , et ces formules étaient peut-être familières aux mathématiciens indiens dès le VIe siècle de notre ère. Le philosophe et astronome Rabbi Abraham ibn Ezra (c. 1140) a établi la symétrie des coefficients binomiaux , tandis qu'une formule fermée a été obtenue plus tard par le talmudiste et mathématicien Levi ben Gerson (mieux connu sous le nom de Gersonides), en 1321. Le triangle arithmétique-un diagramme graphique montrant les relations entre les coefficients binomiaux - a été présenté par des mathématiciens dans des traités remontant au 10ème siècle, et deviendrait finalement connu sous le nom de triangle de Pascal . Plus tard, dans l'Angleterre médiévale , la campanologie a fourni des exemples de ce qui est maintenant connu sous le nom de cycles hamiltoniens dans certains graphiques de Cayley sur les permutations.

A la Renaissance , avec le reste des mathématiques et des sciences , la combinatoire connut une renaissance. Les travaux de Pascal , Newton , Jacob Bernoulli et Euler sont devenus fondateurs dans le domaine émergent. Aux temps modernes, les travaux de JJ Sylvester (fin du XIXe siècle) et de Percy MacMahon (début du XXe siècle) ont contribué à jeter les bases de la combinatoire énumérative et algébrique . La théorie des graphes a également connu une explosion d'intérêt en même temps, en particulier en relation avec le problème des quatre couleurs .

Dans la seconde moitié du 20e siècle, la combinatoire a connu une croissance rapide, qui a conduit à la création de dizaines de nouvelles revues et conférences sur le sujet. En partie, la croissance a été stimulée par de nouvelles connexions et applications à d'autres domaines, allant de l'algèbre aux probabilités, de l'analyse fonctionnelle à la théorie des nombres , etc. Ces connexions effacent les frontières entre la combinatoire et certaines parties des mathématiques et de l'informatique théorique, mais au conduit en même temps à une fragmentation partielle du champ.

Approches et sous-domaines de la combinatoire

Combinatoire énumérative

Cinq arbres binaires sur trois sommets , un exemple de nombres catalans .

La combinatoire énumérative est le domaine le plus classique de la combinatoire et se concentre sur le comptage du nombre de certains objets combinatoires. Bien que compter le nombre d'éléments dans un ensemble soit un problème mathématique assez vaste , de nombreux problèmes qui surviennent dans les applications ont une description combinatoire relativement simple. Les nombres de Fibonacci sont l'exemple de base d'un problème en combinatoire énumérative. La voie douze fois fournit un cadre unifié pour compter les permutations , les combinaisons et les partitions .

Combinatoire analytique

La combinatoire analytique concerne l'énumération de structures combinatoires à l'aide d'outils issus de l' analyse complexe et de la théorie des probabilités . Contrairement à la combinatoire énumérative, qui utilise des formules combinatoires explicites et des fonctions génératrices pour décrire les résultats, la combinatoire analytique vise à obtenir des formules asymptotiques .

Théorie des partitions

La théorie des partitions étudie divers problèmes d'énumération et d'asymptotique liés aux partitions entières et est étroitement liée aux séries q , aux fonctions spéciales et aux polynômes orthogonaux . À l'origine une partie de la théorie et de l' analyse des nombres , elle est maintenant considérée comme une partie de la combinatoire ou un domaine indépendant. Il intègre l' approche bijective et divers outils d'analyse et de théorie analytique des nombres et a des liens avec la mécanique statistique .

La théorie des graphes

Les graphes sont des objets fondamentaux en combinatoire. Les considérations de la théorie des graphes vont de l'énumération (par exemple, le nombre de graphes sur n sommets avec k arêtes) aux structures existantes (par exemple, les cycles hamiltoniens) aux représentations algébriques (par exemple, étant donné un graphe G et deux nombres x et y , est-ce que le Tutte polynôme T G ( x , y ) a une interprétation combinatoire ?). Bien qu'il existe des liens très étroits entre la théorie des graphes et la combinatoire, ils sont parfois considérés comme des sujets distincts. Alors que les méthodes combinatoires s'appliquent à de nombreux problèmes de théorie des graphes, les deux disciplines sont généralement utilisées pour rechercher des solutions à différents types de problèmes.

Théorie de la conception

La théorie de la conception est une étude des conceptions combinatoires , qui sont des collections de sous-ensembles avec certaines propriétés d' intersection . Les conceptions par blocs sont des conceptions combinatoires d'un type spécial. Ce domaine est l'une des parties les plus anciennes de la combinatoire, comme dans le problème d'écolière de Kirkman proposé en 1850. La solution du problème est un cas particulier d'un système de Steiner , lequel systèmes jouent un rôle important dans la classification des groupes simples finis . Le domaine a d'autres liens avec la théorie du codage et la combinatoire géométrique.

Géométrie finie

La géométrie finie est l'étude des systèmes géométriques n'ayant qu'un nombre fini de points. Des structures analogues à celles trouvées dans les géométries continues ( plan euclidien , espace projectif réel , etc.) mais définies de manière combinatoire sont les principaux éléments étudiés. Ce domaine fournit une riche source d'exemples pour la théorie de la conception . Il ne faut pas la confondre avec la géométrie discrète ( géométrie combinatoire ).

Théorie de l'ordre

Diagramme de Hasse de l' ensemble des puissances de {x,y,z} ordonné par inclusion .

La théorie de l'ordre est l'étude des ensembles partiellement ordonnés , à la fois finis et infinis. Divers exemples d'ordres partiels apparaissent en algèbre , géométrie, théorie des nombres et tout au long de la combinatoire et de la théorie des graphes. Les classes notables et les exemples d'ordres partiels incluent les réseaux et les algèbres booléennes .

Théorie des matroïdes

La théorie des matroïdes fait abstraction d'une partie de la géométrie . Il étudie les propriétés des ensembles (généralement des ensembles finis) de vecteurs dans un espace vectoriel qui ne dépendent pas des coefficients particuliers dans une relation de dépendance linéaire . Non seulement la structure mais aussi les propriétés énumératives appartiennent à la théorie des matroïdes. La théorie des matroïdes a été introduite par Hassler Whitney et étudiée dans le cadre de la théorie de l'ordre. C'est maintenant un domaine d'étude indépendant avec un certain nombre de connexions avec d'autres parties de la combinatoire.

Combinatoire extrême

La combinatoire extrême étudie les questions extrêmes sur les systèmes d'ensembles . Les types de questions abordées dans ce cas portent sur le plus grand graphe possible qui satisfait certaines propriétés. Par exemple, le plus grand graphe sans triangle sur 2n sommets est un graphe bipartite complet K n,n . Souvent, il est même trop difficile de trouver exactement la réponse f ( n ) extrême et on ne peut donner qu'une estimation asymptotique .

La théorie de Ramsey est une autre partie de la combinatoire extrême. Il indique que toute configuration suffisamment grande contiendra une sorte d'ordre. C'est une généralisation avancée du principe du pigeonnier .

Combinatoire probabiliste

En combinatoire probabiliste, les questions sont du type suivant : quelle est la probabilité d'une certaine propriété pour un objet discret aléatoire, tel qu'un graphe aléatoire ? Par exemple, quel est le nombre moyen de triangles dans un graphique aléatoire ? Les méthodes probabilistes sont également utilisées pour déterminer l'existence d'objets combinatoires avec certaines propriétés prescrites (pour lesquels des exemples explicites peuvent être difficiles à trouver), simplement en observant que la probabilité de sélectionner au hasard un objet avec ces propriétés est supérieure à 0. Cette approche ( souvent appelée la méthode probabiliste ) révélée très efficace dans les applications à combinatoires et extremes théorie des graphes. Un domaine étroitement lié est l'étude des chaînes de Markov finies , en particulier sur les objets combinatoires. Ici encore, des outils probabilistes sont utilisés pour estimer le temps de mélange .

Souvent associée à Paul Erdős , qui a fait le travail de pionnier sur le sujet, la combinatoire probabiliste était traditionnellement considérée comme un ensemble d'outils pour étudier des problèmes dans d'autres parties de la combinatoire. Cependant, avec la croissance des applications pour analyser les algorithmes en informatique , ainsi que la probabilité classique, la théorie des nombres additifs et la théorie des nombres probabilistes , le domaine s'est récemment développé pour devenir un domaine indépendant de la combinatoire.

Combinatoire algébrique

Schéma d'Young d'une partition (5,4,1).

La combinatoire algébrique est un domaine des mathématiques qui utilise des méthodes d' algèbre abstraite , notamment la théorie des groupes et la théorie des représentations , dans divers contextes combinatoires et, inversement, applique des techniques combinatoires à des problèmes d' algèbre . La combinatoire algébrique étend continuellement son champ d'application, tant dans les sujets que dans les techniques, et peut être considérée comme le domaine des mathématiques où l'interaction des méthodes combinatoires et algébriques est particulièrement forte et significative.

Combinatoire sur les mots

Construction d'un mot infini Thue-Morse .

La combinatoire des mots traite des langages formels . Elle est apparue indépendamment au sein de plusieurs branches des mathématiques, dont la théorie des nombres , la théorie des groupes et les probabilités . Il a des applications en combinatoire énumérative, en analyse fractale , en informatique théorique , en théorie des automates et en linguistique . Alors que de nombreuses applications sont nouvelles, la hiérarchie classique de Chomsky-Schützenberger des classes de grammaires formelles est peut-être le résultat le plus connu dans le domaine.

Combinatoire géométrique

La combinatoire géométrique est liée à la géométrie convexe et discrète , en particulier la combinatoire polyédrique . Il demande, par exemple, combien de faces de chaque dimension un polytope convexe peut avoir. Les propriétés métriques des polytopes jouent également un rôle important, par exemple le théorème de Cauchy sur la rigidité des polytopes convexes. Des polytopes spéciaux sont également considérés, tels que les permutoèdres , les associaèdres et les polytopes de Birkhoff . La géométrie combinatoire est un nom démodé pour la géométrie discrète.

Combinatoire topologique

Fractionnement d'un collier avec deux coupes.

Des analogues combinatoires de concepts et de méthodes en topologie sont utilisés pour étudier la coloration des graphes , la division équitable , les partitions , les ensembles partiellement ordonnés , les arbres de décision , les problèmes de collier et la théorie Morse discrète . Il ne faut pas le confondre avec la topologie combinatoire qui est un nom plus ancien pour la topologie algébrique .

Combinatoire arithmétique

La combinatoire arithmétique est née de l'interaction entre la théorie des nombres , la combinatoire, la théorie ergodique et l'analyse harmonique . Il s'agit d'estimations combinatoires associées à des opérations arithmétiques (addition, soustraction, multiplication et division). La théorie additive des nombres (parfois aussi appelée combinatoire additive) fait référence au cas particulier où seules les opérations d'addition et de soustraction sont impliquées. Une technique importante en arithmétique combinatoire est la théorie ergodique des systèmes dynamiques .

Combinatoire infini

La combinatoire infinitive, ou théorie des ensembles combinatoires, est une extension des idées de la combinatoire aux ensembles infinis. Il fait partie de la théorie des ensembles , un domaine de la logique mathématique , mais utilise des outils et des idées de la théorie des ensembles et de la combinatoire extrême.

Gian-Carlo Rota a utilisé le nom de combinatoire continue pour décrire la probabilité géométrique , car il existe de nombreuses analogies entre compter et mesurer .

Domaines connexes

Optimisation combinatoire

L'optimisation combinatoire est l'étude de l'optimisation sur des objets discrets et combinatoires. Il a commencé dans le cadre de la combinatoire et de la théorie des graphes, mais est maintenant considéré comme une branche des mathématiques appliquées et de l'informatique, liée à la recherche opérationnelle , à la théorie des algorithmes et à la théorie de la complexité computationnelle .

Théorie du codage

La théorie du codage a commencé dans le cadre de la théorie de la conception avec les premières constructions combinatoires de codes de correction d'erreurs . L'idée principale du sujet est de concevoir des méthodes efficaces et fiables de transmission de données. C'est maintenant un vaste domaine d'étude, faisant partie de la théorie de l' information .

Géométrie discrète et computationnelle

La géométrie discrète (également appelée géométrie combinatoire) a également commencé dans le cadre de la combinatoire, avec des résultats précoces sur les polytopes convexes et les nombres qui s'embrassent . Avec l'émergence des applications de la géométrie discrète à la géométrie computationnelle , ces deux domaines ont partiellement fusionné et sont devenus un domaine d'étude distinct. Il reste de nombreux liens avec la combinatoire géométrique et topologique, qui eux-mêmes peuvent être considérés comme des excroissances de la première géométrie discrète.

Combinatoire et systèmes dynamiques

Les aspects combinatoires des systèmes dynamiques sont un autre domaine émergent. Ici, des systèmes dynamiques peuvent être définis sur des objets combinatoires. Voir par exemple système dynamique graphique .

Combinatoire et physique

Il existe des interactions croissantes entre la combinatoire et la physique , en particulier la physique statistique . Les exemples incluent une solution exacte du modèle d'Ising et une connexion entre le modèle de Potts d'une part, et les polynômes chromatiques et Tutte d' autre part.

Voir également

Remarques

Les références

Liens externes