Théorie > Combinatoire

Informations

Chaque chapitre est constitué de points théoriques et d'exercices. Ces derniers ont pour but de vérifier que la théorie a bien été assimilée. Ils rapportent chacun entre 3 et 12 points, selon leur difficulté. Pour compléter un chapitre, il faut résoudre tous ses exercices.

Certains chapitres ont d'autres chapitres pour prérequis. Pour accéder aux exercices d'un tel chapitre, il est nécessaire de d'abord compléter ses chapitres prérequis.

Introduction

La combinatoire étudie principalement les collections finies d'objets et peut prendre des formes très diverses. Ainsi, les problèmes de dénombrement, de pavages, ou encore de théorie des graphes sont considérés comme des problèmes de combinatoire. Nous donnons ici toute la théorie nécessaire concernant ces différents thèmes ainsi que des exemples illustrant les différentes méthodes de résolution de ces problèmes.

Chapitres

Les chapitres de cette section sont ordonnés selon leur importance (des plus primordiaux aux plus avancés).

Les essentiels

Les chapitres suivants reprennent la théorie essentielle relative à cette section.

Principe des tiroirs

Le principe des tiroirs est un principe important qui peut servir dans des contextes variés. Il est également appelé principe de Dirichlet ou pigeonhole principle en anglais. Ce principe, qui peut a priori sembler trivial, permet pourtant dans certains cas de résoudre des situations très complexes.

Exercices

Statistiques

Complété par 1316 personnes
Taux de réussite : 75%

Dénombrement

Bon nombre de problèmes de combinatoire consistent à dénombrer les façons d'effectuer une certaine tâche. On pourra ainsi se demander de combien de manières il est possible de placer des convives autour d'une table ou encore combien il existe de tirages différents au Lotto. Il existe pour ce faire plusieurs formules s'appliquant à différents cas. Nous présentons dans ce chapitre toutes les formules de permutations, combinaisons et arrangements, ainsi que des exemples d'utilisation de celles-ci.

Exercices

Statistiques

Complété par 491 personnes
Taux de réussite : 41%

Pavages

Les problèmes de pavages constituent une classe de problèmes assez particulière. Ils consistent à paver une surface donnée à l'aide de certains pavés de forme donnée, et le tout est généralement de montrer qu'un tel pavage est impossible. Nous présentons ici les différentes méthodes permettant de résoudre ce type de problème.

Pour pouvoir accéder aux exercices de ce chapitre, vous devez d'abord compléter : Principe des tiroirs

Exercices

Statistiques

Complété par 477 personnes
Taux de réussite : 63%

Coefficients binomiaux

Les coefficients binomiaux $C_n^k$ définis précédemment ont en fait de nombreuses propriétés, des plus basiques aux plus surprenantes. Il est important de bien connaître celles-ci puisque, en plus d'être divertissantes, elles permettent aussi de simplifier des formules a priori compliquées obtenues lors d'un dénombrement. Le triangle de Pascal permet de représenter les différents coefficients binomiaux de sorte à mettre en évidence plusieurs de ces propriétés.

Pour pouvoir accéder aux exercices de ce chapitre, vous devez d'abord compléter : Dénombrement

Exercices

Statistiques

Complété par 426 personnes
Taux de réussite : 94%

Les classiques

Les chapitres suivants, un peu plus avancés, reprennent les résultats classiques de cette section.

Invariants et (mono)variants

Bien que la notion d'invariant soit assez simple à comprendre, elle reste un outil très puissant pour résoudre des problèmes de combinatoire. De manière un peu plus générale, on peut également utiliser des monovariants ou des variants pour mieux comprendre certaines situations non évidentes.

Exercices

Statistiques

Complété par 286 personnes
Taux de réussite : 29%

Théorie des graphes

Nous présentons dans ce chapitre la notion de graphe et expliquons comment des graphes peuvent être cachés derrière des problèmes divers et variés. Nous donnons ensuite quelques résultats concernant les graphes eulériens et les graphes planaires. Enfin, nous voyons en quoi le coloriage des graphes peut s'avérer utile et énonçons un résultat fondamental dans ce sujet : le théorème de Ramsey.

Pour pouvoir accéder aux exercices de ce chapitre, vous devez d'abord compléter : Principe des tiroirs

Exercices

Statistiques

Complété par 367 personnes
Taux de réussite : 58%

Dénombrement (suite)

Nous avons vu précédemment comment dénombrer des possibilités à l'aide des formules de permutations, combinaisons et arrangements. Il n'est pas toujours possible d'appliquer ces formules directement, et l'objectif de ce chapitre est de présenter différentes méthodes permettant de résoudre certaines situations plus complexes.

Pour pouvoir accéder aux exercices de ce chapitre, vous devez d'abord compléter : Coefficients binomiaux

Exercices

Statistiques

Complété par 210 personnes
Taux de réussite : 61%

Les pointus

Les chapitres suivants reprennent des notions plus rarement utiles en compétition mais qui peuvent devenir assez puissantes si bien maitrisées.

Double comptage

Ce chapitre présente la méthode du double comptage, qui permet de démontrer des résultats théoriques comme la formule de Cayley mais qui se révèle surtout être un outil très puissant pour démontrer des problèmes de combinatoire de haut niveau.

Pour pouvoir accéder aux exercices de ce chapitre, vous devez d'abord compléter : Théorie des graphes - Dénombrement (suite)

Exercices

Statistiques

Complété par 160 personnes
Taux de réussite : 84%