|
Édition du: 17/09/2026 |
|
INDEX |
COMBINATOIRE |
|||
Faites un double-clic pour un retour en haut de page
Panorama des
notions avancées de combinatoire – Diconombre
Page du Dictionnaire des nombres (diconombre.fr)
consacrée aux notions avancées de la combinatoire. Au lycée, la
combinatoire apprend à dénombrer des objets, des choix, des arrangements, des
permutations ou des répartitions. Après le baccalauréat, le domaine change
d’échelle. La question reste souvent «
combien ? », mais les objets à compter deviennent plus complexes et
les méthodes beaucoup plus nombreuses. Cette page
propose un tour d’horizon de la
combinatoire post-bac. Elle ne cherche pas à développer les notions ni
à présenter un cours universitaire complet. Son objectif est de donner une
carte du territoire : reconnaître les principales notions, comprendre leur
rôle et découvrir les relations qui les unissent.
|
||
|
|
Sommaire de cette page >>> Outils avancés
du dénombrement >>> Grandes
familles de nombres combinatoires >>> Partitions,
compositions et structures associées >>> Symétries et
dénombrement à équivalence près >>>
Structures combinatoires >>>
Énumération et comportement des grandes tailles >>>
Vers les frontières de la combinatoire >>>
Bilan |
Débutants Glossaire |
Orientation
|
La combinatoire commence par une
question simple: Combien
y en a-t-il ? :
Voir Le monde complet de la
combinatoire Mais, elle conduit rapidement à une
question beaucoup plus vaste : Quelles
structures
se cachent derrière ce nombre ? : |
|
Les
principes élémentaires — addition, multiplication, complément,
inclusion-exclusion, bijection, double comptage — ont été présentés dans la
page consacrée aux méthodes de dénombrement. À un niveau
plus avancé, ces mêmes idées conduisent à des outils capables de traiter des
familles d'objets beaucoup plus complexes.
Ces outils
ne constituent plus seulement des recettes de calcul : ils permettent de faire apparaître la structure cachée
derrière un dénombrement. Récurrences combinatoires Une récurrence exprime le nombre
d'objets de taille n à partir de nombres correspondant à des tailles plus
petites. C'est une situation très
fréquente en combinatoire. Plutôt que de chercher directement une formule, on
décompose les objets selon une caractéristique simple. Par exemple, le nombre de façons de monter un
escalier de n marches en faisant des pas de 1 ou de 2 marches vérifie : Pour atteindre la marche n, le dernier pas vient
nécessairement de la marche n – 1 ou de la marche n – 2. Cette idée toute simple
conduit à des récurrences beaucoup plus complexes et constitue un outil
essentiel de la combinatoire énumérative. Fonctions génératrices Une suite de nombres
peut être transformée en une expression qui contient tous ses termes. À une suite:
Le nombre Cette transformation
peut rendre beaucoup plus simples certaines opérations combinatoires. Une
addition de familles correspond à une addition de fonctions ; la combinaison
indépendante de deux familles conduit naturellement à un produit. Par exemple, si un objet est constitué d'une
première partie choisie de i façons et d'une seconde partie choisie de j
façons, les coefficients du produit des deux fonctions génératrices comptent
les possibilités obtenues pour Les fonctions génératrices exponentielles
jouent un rôle particulier lorsque les objets sont étiquetés. Les fonctions
génératrices sont donc un pont entre : objets combinatoires →
nombres → séries algébriques. Séries formelles Une fonction génératrice
peut être considérée non comme une fonction destinée à être calculée pour une
valeur de x, mais comme une série de
coefficients que l'on manipule algébriquement. On parle alors de série formelle. Cette distinction devient importante en combinatoire
: il n'est pas toujours nécessaire de savoir si une série converge. Ce qui
intéresse d'abord le mathématicien, ce sont ses coefficients et les
opérations qui permettent de les déterminer. Les séries formelles
fournissent ainsi un langage indispensable pour traduire des constructions
combinatoires en calculs algébriques. Inclusion-exclusion et méthodes de tamis Le principe
d'inclusion-exclusion est connu dès le lycée : pour compter les éléments appartenant
à plusieurs ensembles, on additionne, soustrait, puis réintroduit les
intersections nécessaires. À un niveau avancé, ce
principe devient une véritable famille de méthodes. Les méthodes de tamis permettent
notamment de compter des objets qui évitent simultanément plusieurs
propriétés indésirables. Un exemple classique est celui des permutations
sans point fixe, les dérangements. On peut compter directement les
permutations interdites ou utiliser l'inclusion-exclusion pour éliminer progressivement
celles qui possèdent au moins un élément à sa place. Inversion combinatoire et inversion de Möbius Certaines situations
donnent deux suites de nombres reliées par une relation de sommation. Une formule d'inversion permet alors de
retrouver l'une à partir de l'autre. L'inversion de Möbius généralise cette
idée. Elle s'applique notamment aux ensembles munis d'un ordre, appelés posets. Sans entrer dans son
formalisme, l'idée peut être résumée ainsi : une information obtenue par accumulation peut
parfois être reconstruite en retirant précisément les contributions déjà
comptées. L'inversion de Möbius
intervient dans de nombreux problèmes de combinatoire et établit aussi des
liens avec la théorie des nombres. |
|
|
La
combinatoire a produit, ou utilise constamment, de nombreuses familles de
nombres remarquables. Les coefficients
binomiaux et multinomiaux prolongent les combinaisons étudiées au lycée. Le
triangle de Pascal révèle leurs nombreuses relations. Les nombres
de Stirling comptent notamment des partitions d'ensembles ou des répartitions
liées aux permutations. Les nombres de Bell donnent le nombre total de
partitions d'un ensemble. Les nombres
d'Euler apparaissent notamment dans l'étude des permutations et de leurs
montées et descentes. Les nombres de
Catalan constituent une famille particulièrement riche : une même suite
compte des objets aussi différents que des chemins de Dyck, certains arbres,
des parenthésages ou des triangulations. À leurs
côtés apparaissent les nombres de Motzkin, de
Schröder, de Fuss-Catalan, de Narayana et de nombreuses autres suites. La
combinatoire offre ainsi un véritable monde de nombres remarquables, souvent
reliés entre eux par des identités, des récurrences ou des interprétations
multiples. Coefficients binomiaux et multinomiaux Le coefficient binomial
compte le nombre de façons de choisir k objets parmi n.
Mais cette définition
élémentaire n'est que le début. Les coefficients binomiaux apparaissent dans
les développements algébriques, les identités combinatoires, les probabilités
et de nombreuses récurrences. Les coefficients multinomiaux
généralisent cette situation lorsqu'un ensemble doit être partagé en
plusieurs catégories. Par exemple, si 10 personnes doivent être réparties
en trois groupes de tailles 4, 3 et 3, le nombre de répartitions est :
Nombres de Stirling Il existe deux grandes
familles de nombres de Stirling. Les nombres de Stirling
de seconde espèce comptent notamment les façons de partitionner n éléments en
k sous-ensembles non vides. Ainsi,
car un ensemble de quatre éléments peut être
partagé en deux blocs de sept façons. Les nombres de Stirling
de première espèce sont liés aux permutations
et à leur nombre de cycles. Ces deux familles
montrent une caractéristique importante de la combinatoire : un même type de
structure peut être étudié sous plusieurs points de vue, et les nombres
obtenus deviennent eux-mêmes des objets d'étude. Nombres de Bell Le nombre de Bell Bn
donne le nombre total de partitions d'un ensemble de n éléments. Pour quatre éléments :
Il existe donc 15 façons différentes de partager
quatre objets en groupes non vides, sans tenir compte de l'ordre des groupes. Les nombres de Bell sont
reliés aux nombres de Stirling par :
Ils constituent ainsi un
exemple particulièrement clair de la manière dont plusieurs familles de
nombres combinatoires s'emboîtent. Nombres d'Euler Les nombres d'Euler apparaissent
notamment dans l'étude des permutations selon le nombre de montées et de
descentes. Dans une permutation comme
on peut observer à chaque position si la suite
monte ou descend. Ce type de propriété permet
de classer les permutations et de les dénombrer selon leur structure interne. La combinatoire ne
s'intéresse donc plus seulement au nombre total des permutations, mais à la répartition des permutations selon
certaines propriétés. Nombres de Catalan Les nombres de Catalan constituent l'une
des familles les plus célèbres de la combinatoire. Ils apparaissent dans un
grand nombre de problèmes apparemment différents :
Par exemple, le nombre de façons de placer
correctement trois paires de parenthèses est :
Le phénomène remarquable
est que la même suite compte des
objets de natures très différentes. C'est précisément ce
genre de correspondance que recherche la combinatoire. Autres familles remarquables Autour de ces grandes
familles se trouvent de nombreuses autres suites :
Certaines généralisent
une famille connue ; d'autres apparaissent dans une classe particulière de
chemins, d'arbres, de partitions ou de permutations. |
|
|
Au-delà du
choix et de l'ordre des objets, la combinatoire étudie leur décomposition et leur
organisation. Une
partition d'un entier représente celui-ci comme une somme d'entiers positifs,
sans tenir compte de l'ordre. Une composition conserve au contraire cet
ordre. Une
partition d'un ensemble consiste à le diviser en sous-ensembles non vides,
sans ordre entre ces sous-ensembles. Ces objets
conduisent naturellement aux nombres de Stirling et de Bell, mais aussi aux
diagrammes de Ferrers, aux diagrammes de Young et
aux tableaux de Young. À un niveau encore
plus avancé, ces structures sont liées à la combinatoire algébrique et à la
théorie des représentations. L'idée
essentielle est ici de ne plus considérer seulement combien d'objets choisir,
mais comment une structure peut être décomposée ou organisée. Partitions d'un entier Une partition de 7 peut être écrite :
L'ordre des termes n'est
pas pris en compte : 1 + 4 et 4 + 1
représentent la même partition. Le nombre de partitions de
n, généralement noté p(n), augmente rapidement avec n. Compositions Une composition conserve l'ordre. Ainsi 4 + 2 + 1 et 1 + 4 + 2 sont deux
compositions différentes du même entier. Cette distinction entre
partition et composition est simple, mais elle conduit à deux univers
combinatoires très différents. Les compositions
apparaissent notamment lorsqu'une quantité doit être découpée en portions ordonnées. Partitions d'ensembles Une partition d'un ensemble
est une division de ses éléments en groupes non vides. Avec :
on peut avoir par exemple :
ou
L'ordre des groupes n'a
pas d'importance. Cette notion est
directement reliée aux nombres de
Stirling de seconde espèce et aux nombres de Bell. Diagrammes et tableaux de Young Les partitions d'entiers
peuvent être représentées graphiquement par des diagrammes de Young. Pour la partition 5 + 3 + 1, on dessine trois
lignes contenant respectivement 5, 3 et 1 cases. Cette représentation
simple permet d'étudier des propriétés beaucoup plus riches des partitions. Les tableaux de Young, obtenus en
remplissant ces diagrammes selon certaines règles, interviennent ensuite en
combinatoire algébrique et dans la théorie des représentations. |
|
|
Une
difficulté nouvelle apparaît lorsque deux configurations doivent être
considérées comme identiques parce qu'elles ne diffèrent que par une
symétrie. Deux
colliers, par exemple, peuvent représenter le même objet si l'on peut passer
de l'un à l'autre par une rotation. Le problème n'est alors plus simplement
de compter les configurations, mais de compter les configurations distinctes
à symétrie près. Le lemme de
Burnside fournit une méthode générale pour ce type de dénombrement. Le
théorème d'énumération de Pólya en constitue un développement
particulièrement puissant, notamment pour les problèmes de coloriage. Cette approche
conduit à étudier les actions de groupes, les classes d'équivalence, les
objets cycliques et les graphes considérés à isomorphisme près. C'est une
étape importante dans le passage de la combinatoire élémentaire à la
combinatoire structurale : Il ne suffit
plus de compter les objets ; il faut déterminer quand deux objets doivent
être considérés comme les mêmes. Pourquoi les symétries changent le problème Imaginons quatre couleurs disposées sur les
quatre côtés d'un carré. Si le carré peut être tourné, deux coloriages
obtenus par une rotation peuvent représenter le même objet. Compter les coloriages bruts ne suffit donc plus. Il faut décider quelles
transformations sont autorisées et considérer comme identiques les
configurations reliées par ces transformations. C'est le principe du dénombrement à équivalence près. Lemme de Burnside Le lemme de Burnside fournit une
méthode générale pour ce type de problème. L'idée est de regarder, pour chaque transformation
autorisée, combien de configurations restent inchangées par cette
transformation, puis de combiner ces nombres. Sans entrer dans la
démonstration, le principe peut se résumer ainsi : pour compter les configurations réellement différentes, on tient compte
des configurations qui restent fixes sous les symétries. Cette méthode est très
utile pour les rotations, réflexions, coloriages, colliers ou bracelets. Théorie de Pólya Le théorème d'énumération de Pólya développe
cette idée et permet notamment de traiter systématiquement des problèmes de
coloriage soumis à des symétries. Un même problème peut
alors être posé sous différentes formes :
La théorie de Pólya
fournit un cadre général à ces questions. |
|
|
La combinatoire
avancée s'intéresse à des objets qui possèdent une structure interne. Les arbres
constituent une première famille fondamentale. Ils interviennent dans le
dénombrement, les algorithmes et la représentation de nombreuses structures. Les graphes
permettent de représenter des relations entre des objets : réseaux, chemins,
connexions, colorations, circuits. On distingue notamment graphes étiquetés
et non étiquetés, graphes orientés ou non orientés. Les hypergraphes
généralisent les graphes lorsque les relations peuvent concerner plusieurs
sommets simultanément. D'autres
structures apparaissent avec les mots et les langages, les ensembles
partiellement ordonnés (posets) et les treillis. La question
combinatoire devient alors : Combien
existe-t-il de structures possédant telles propriétés ? Cette
question est à l'origine de vastes domaines de la combinatoire moderne. Arbres Un arbre est un graphe connexe qui ne
contient pas de cycle. Cette définition très
simple donne naissance à une immense famille de structures. Les arbres interviennent dans les arbres
généalogiques, les arbres de décision, les expressions mathématiques, les
structures de données informatiques et les algorithmes. La combinatoire peut
poser des questions comme : Combien existe-t-il
d'arbres possédant Ou encore : Combien existe-t-il
d'arbres ayant une certaine forme ? Le nombre d'arbres étiquetés à n sommets est
notamment donné par la célèbre formule
de Cayley : nn-2. Pour Graphes Un graphe est constitué de sommets
reliés par des arêtes. Il permet de représenter
une multitude de situations : réseaux de transport, relations entre
personnes, connexions informatiques, dépendances entre tâches, etc. La combinatoire peut alors chercher à dénombrer
les graphes ayant :
On distingue notamment
les graphes étiquetés, où les sommets
sont identifiés, et les graphes non
étiquetés, où seuls les liens entre sommets comptent. Cette distinction
devient essentielle lorsque l'on veut éviter de compter plusieurs fois une
même structure. Hypergraphes Dans un graphe
ordinaire, une arête relie deux sommets. Dans un hypergraphe, une hyperarête
peut relier trois, quatre ou davantage de sommets. Cette généralisation
permet de représenter des relations entre plusieurs objets simultanément. Elle apparaît notamment dans
certains problèmes de couverture, de classification, de réseaux et de
combinatoire extrémale. Mots et langages (anagrammes) Un mot est une suite de
symboles provenant d'un alphabet. Avec l'alphabet {0, 1},
les mots de longueur 3 sont par exemple :
Il y en a Mais les questions
deviennent rapidement plus intéressantes lorsqu'on impose des contraintes :
La combinatoire des mots rejoint alors
l'informatique théorique et l'étude des langages formels. Ensembles ordonnés et posets Dans la vie courante
comme en mathématiques, certaines relations imposent un ordre entre les objets. Mais cet
ordre n'est pas toujours un classement complet. Imaginons par exemple plusieurs tâches à réaliser
pour construire une maison. Il faut terminer les fondations avant de monter les
murs, et les murs avant de poser le toit. En revanche, la pose des fenêtres
et l'installation électrique peuvent être réalisées indépendamment : ces deux
tâches ne sont pas nécessairement comparables. On peut donc avoir : A
< B, B < C sans avoir nécessairement de relation entre A et D. Un ensemble muni d'une
relation d'ordre de ce type est appelé ensemble partiellement ordonné, ou poset (partially ordered set).
« Partiellement » signifie que certains
éléments sont comparables et que d'autres ne le sont pas. Les posets
permettent ainsi de représenter des dépendances,
des hiérarchies, des priorités ou des contraintes d'ordre. Ils
interviennent notamment dans l'organisation de tâches, les algorithmes et la
combinatoire. On peut représenter un poset
par un diagramme de Hasse, dans lequel les relations essentielles entre les
éléments sont dessinées sous forme de liens. Les treillis constituent une famille
particulière de posets : pour deux éléments, ils permettent
notamment de définir un plus petit élément qui leur est supérieur à tous deux
et un plus grand élément qui leur est inférieur à tous deux. Enfin, les posets fournissent le cadre naturel de l'inversion de Möbius, évoquée
précédemment. Cette relation montre que les structures d'ordre ne servent pas
seulement à organiser les objets : elles deviennent aussi des outils de dénombrement. |
|
|
Dénombrer exactement
les objets de taille n est une première étape. Une autre question apparaît
lorsque n devient très grand : Comment le nombre d'objets évolue-t-il ? La
combinatoire énumérative étudie les suites obtenues en comptant des familles
d'objets. Elle recherche des formules, des récurrences, des fonctions
génératrices ou des relations entre différentes suites. Lorsque les
nombres deviennent très grands, on s'intéresse à leur comportement asymptotique
: ordre de grandeur, croissance, approximation et comportement lorsque la
taille tend vers l'infini. La formule
de Stirling, par exemple, permet d'approcher les grandes factorielles et
devient un outil fondamental pour comprendre le comportement de nombreux
nombres combinatoires. La
combinatoire ne cherche donc plus seulement une réponse exacte à la question
« combien ? », mais aussi à la question : À quelle vitesse ce nombre
grandit-il ? Suites énumératives Si an représente
le nombre d'objets de taille n, on obtient une suite énumérative : Une partie importante de
la combinatoire consiste à découvrir les propriétés de telles suites. On recherche notamment :
Croissance des nombres combinatoires Les nombres
combinatoires peuvent croître extrêmement rapidement. La factorielle n! en est un exemple simple. Pour n = 10, 10! = 3 628 000 et pour n = 20, 20! ≈ 2,43 × 1018 Le nombre de configurations devient rapidement
gigantesque. La combinatoire cherche
donc également à comprendre la
vitesse de croissance des nombres qu'elle produit. Combinatoire asymptotique Lorsque n devient très
grand, une formule exacte peut être moins utile qu'une bonne approximation. La formule de Stirling donne par exemple :
Le symbole La combinatoire asymptotique étudie
ainsi le comportement des suites énumératives lorsque leur paramètre devient
grand. À un niveau plus avancé
encore apparaissent l'analyse des fonctions génératrices, l'étude de leurs
singularités et diverses méthodes issues de l'analyse mathématique. |
|
|
La
combinatoire ne constitue pas un domaine isolé. Ses méthodes et ses structures
rencontrent de nombreuses autres branches des mathématiques et de
l'informatique. Combinatoire et autres
mathématiques
Combinatoire et informatique Les liens
avec l'informatique sont particulièrement étroits. Les
problèmes de génération de configurations, de dénombrement, d'optimisation et
de recherche dans de grands espaces de possibilités conduisent à des
algorithmes combinatoires. La
combinatoire intervient également dans les graphes et réseaux, les langages
formels, la théorie des codes, la cryptographie et l'étude de la complexité
des problèmes de comptage. La question
du nombre de configurations possibles devient alors aussi une question de
temps de calcul et de faisabilité. Vers la recherche contemporaine Certaines
directions deviennent très spécialisées : combinatoire analytique, combinatoire
bijective, structures aléatoires, géométrie combinatoire, modèles issus de la
physique mathématique, etc. Elles
montrent que la combinatoire continue de produire de nouvelles méthodes et de
nouveaux objets, souvent à la frontière de plusieurs disciplines. Combinatoire algébrique La combinatoire algébrique étudie les
liens entre structures combinatoires et objets algébriques. Les partitions, tableaux
de Young, permutations, fonctions symétriques et polynômes combinatoires en constituent
quelques exemples. Une structure
combinatoire peut ainsi être représentée par un objet algébrique, et
inversement une propriété algébrique peut parfois être comprise grâce à une
interprétation combinatoire. Combinatoire probabiliste La probabilité peut
devenir un outil de démonstration. Supposons qu'on cherche à montrer qu'il existe au
moins un objet possédant une propriété particulière. On peut construire un
objet au hasard et montrer que la probabilité qu'il possède cette propriété est
strictement positive. Alors un tel objet existe nécessairement. C'est l'idée générale de
la méthode probabiliste,
associée notamment aux travaux de Paul Erdős. Elle est utilisée dans
l'étude des graphes, des configurations aléatoires et de nombreux problèmes
d'existence. Combinatoire extrémale La combinatoire
extrémale pose des questions du type : Quelle est la taille
maximale d'une famille d'objets qui respecte telle contrainte ? Par exemple, combien peut-on choisir de sous-ensembles
parmi les sous-ensembles d'un ensemble donné sans qu'aucun ne contienne un
autre ? On ne cherche donc plus
nécessairement à compter tous
les objets, mais à déterminer une valeur maximale ou minimale compatible avec
certaines règles. Géométrie combinatoire La géométrie combinatoire s'intéresse
aux propriétés discrètes des configurations géométriques. Combien de régions peut-on obtenir avec des
droites ? Combien de façons de relier certains points ? Quelle est la structure d'un arrangement de plans
? La géométrie fournit les
objets ; la combinatoire étudie leurs configurations et leurs relations. Combinatoire additive et théorie des nombres La combinatoire additive étudie
notamment ce qui se produit lorsqu'on additionne les éléments d'un ensemble
de nombres. Pour un ensemble A, on peut considérer :
La question devient alors : quelle peut être la
taille de A + A? Quelles structures possède-t-il ? Ces questions établissent
des liens étroits entre combinatoire et théorie des nombres. Combinatoire et informatique L'informatique rencontre
la combinatoire dès qu'un problème comporte un grand nombre de possibilités. Pour un problème possédant 2n
configurations, le nombre de possibilités double à chaque augmentation de n
d'une unité. La question n'est donc plus seulement : Combien
existe-t-il de solutions ? Mais aussi : Peut-on les produire ? Les compter ?
Les rechercher efficacement ? Cela conduit à la génération combinatoire, à la
programmation dynamique, aux algorithmes sur les graphes, à l'optimisation
combinatoire et à l'étude de la complexité des problèmes de comptage. Théorie des codes La combinatoire
intervient également dans la conception de codes permettant de détecter ou de corriger des erreurs. Un code peut être considéré comme une famille de
mots sélectionnés selon certaines règles. Il faut alors choisir suffisamment de mots pour transmettre
beaucoup d'informations tout en maintenant une distance suffisante entre eux
afin de pouvoir détecter ou corriger certaines erreurs. La théorie des codes
constitue ainsi un exemple concret d'une rencontre entre combinatoire,
algèbre et informatique. Vers la recherche contemporaine Les frontières du
domaine sont difficiles à délimiter. La combinatoire
analytique associe dénombrement et analyse mathématique. La combinatoire
bijective recherche des correspondances directes entre familles d'objets.
Les structures
aléatoires étudient les propriétés qui apparaissent dans des objets
combinatoires de grande taille. D'autres travaux font
intervenir la géométrie, l'algèbre, la théorie des nombres ou même des
modèles provenant de la physique
mathématique. À ce niveau, la
combinatoire n'est plus seulement une boîte à outils pour compter. Elle
devient un lieu où se rencontrent de nombreuses branches des mathématiques. |
|
|
De « combien ? » à « quelle structure ? » La combinatoire
élémentaire part d'une situation concrète : choisir, placer, ordonner,
répartir. La
combinatoire avancée conserve cette question du dénombrement, mais elle
change progressivement de perspective. On apprend à transformer un problème, à
reconnaître une structure, à
exploiter une symétrie, à
représenter une famille entière par une fonction génératrice, à comparer des objets par une bijection, puis à étudier
l'évolution du nombre d'objets lorsque leur taille augmente. Ainsi, une question apparemment
simple "Combien y en a-t-il
?" peut conduire à des questions beaucoup plus vastes :
La combinatoire commence par l'art de compter.
Elle devient progressivement l'étude des structures discrètes, de leurs
symétries, de leur énumération et de leurs relations avec les autres
mathématiques. |
|
Suite |
|
|
Retour |
|
|
Je
débute |
|
|
Voir |
|
|
|