Théorie > Combinatoire

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

L'accès aux exercices d'un chapitre est autorisé à partir du moment où ses chapitres prérequis ont été complétés, c'est-à-dire quand tous les exercices de ceux-ci ont été résolus.

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.

Théorie

Exercices

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.

Théorie

Exercices

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.

Théorie

Exercices

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 et ainsi le compléter, vous devez d'abord compléter : Principe des tiroirs

Théorie

Exercices

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 et ainsi le compléter, vous devez d'abord compléter : Dénombrement

Théorie

Exercices

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 et ainsi le compléter, vous devez d'abord compléter : Principe des tiroirs

Théorie

Exercices

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 et ainsi le compléter, vous devez d'abord compléter : Coefficients binomiaux

Théorie

Exercices

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 et ainsi le compléter, vous devez d'abord compléter : Dénombrement (suite) - Théorie des graphes

Théorie

Exercices