Combinatoire et Dénombrement

Introduction

Les méthodes de démonstration en combinatoire sont essentielles pour prouver des propriétés concernant le dénombrement d'objets combinatoires. Deux outils principaux sont abordés ici : la démonstration par récurrence et la méthode combinatoire directe.

1. La démonstration par récurrence

Principe

La démonstration par récurrence permet d'établir qu'une propriété P(n) est vraie pour tout entier naturel n à partir de deux étapes :

1. Initialisation : Vérifier que P(n0) est vraie pour un entier n0 donné.
2. Étape de recurrence : Montrer que si P(k) est vraie, alors P(k+1) l'est aussi.

Exemple

Propriété : La somme des n premiers entiers est donnée par S_n = n(n+1)/2.

Initialisation :
Pour n=1, S₁=1, et 1·(1+1)/2=1, donc vrai.

Recurrence :
Supposons que P(k) : S_k= k(k+1)/2 est vraie. Calculons S_k+1 :

• S_k+1= S_k + (k+1)
• = k(k+1)/2 + (k+1)
• = (k(k+1)+2(k+1))/2 = (k+1)(k+2)/2

Donc P(k+1) est vrai et la propriété est démontrée par récurrence.

2. La méthode combinatoire

Principe

Cette méthode consiste à interpréter le problème de dénombrement comme un comptage direct d'objets ou d'ensembles de manière constructive ou bijective.

Exemple : Combinatoire directe

Compte le nombre de façons de choisir 3 éléments parmi n, c'est le coefficient binomial C(n,3).

La formule : C(n,3) = n(n-1)(n-2)/6.

Ce résultat s'obtient directement en considérant
le nombre de triplets distincts possibles sans répétition.

Résumé

• Les démonstrations par récurrence sont utiles pour prouver des propriétés générales.
• La méthode combinatoire se concentre sur le dénombrement direct d'ensembles.

Conclusion

Ces deux méthodes sont complémentaires : la récurrence permet de prouver des propriétés générales, tandis que la méthode combinatoire fournit des dénombrements explicites ou des interprétations combinatoires pour les problèmes.