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

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 644 personnes
Taux de réussite : 79%

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 149 personnes
Taux de réussite : 27%

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 245 personnes
Taux de réussite : 45%

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 233 personnes
Taux de réussite : 64%

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 204 personnes
Taux de réussite : 92%

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 203 personnes
Taux de réussite : 61%

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 101 personnes
Taux de réussite : 56%

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 : Dénombrement (suite) - Théorie des graphes

Exercices

Statistiques

Complété par 80 personnes
Taux de réussite : 88%