Combinatoire et Dénombrement : Concepts Clés

Principes de base et k-uplets

La combinatoire repose sur deux principes fondamentaux. Le principe additif établit que pour deux ensembles disjoints A et B contenant respectivement m et n éléments, Card(A∪B) = m + n. Le principe multiplicatif concerne le produit cartésien d'ensembles, où le nombre d'éléments est le produit des cardinaux.

Un k-uplet d'un ensemble E est une liste ordonnée de k éléments, distincts ou non. Pour un ensemble E à n éléments, l'ensemble de tous les k-uplets possibles est noté E^k et contient n^k éléments. Une partie de E est simplement un sous-ensemble de E. L'ensemble de toutes les parties de E est noté P(E) et contient 2^n éléments.

Quand on parle de k-uplets d'éléments distincts, tous les éléments doivent être différents et l'ordre compte. Leur nombre est donné par la formule nn-1$$n-2...$n-(k-1)$ = n!/$n-k$!. Une permutation est un cas particulier : c'est un n-uplet d'éléments distincts, et il en existe n! (factorielle de n).

💡 On peut visualiser les parties d'un ensemble E en associant à chaque partie un code binaire où 1 signifie que l'élément appartient à la partie et 0 qu'il n'y appartient pas. C'est pourquoi il y a exactement 2^n parties!

Combinaisons et coefficients binomiaux

Les combinaisons sont des parties de k éléments d'un ensemble E, où l'ordre n'a pas d'importance et sans répétition. Le nombre de combinaisons de k éléments parmi n est noté $\binom{n}{k}$ (coefficient binomial) et se calcule par la formule $\binom{n}{k} = \frac{n!}{(n-k)!k!}$.

Les coefficients binomiaux possèdent des propriétés intéressantes. Par exemple, $\binom{n}{k} = \binom{n}{n-k}$ et $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$ (relation de Pascal). Cette dernière propriété permet de construire le célèbre triangle de Pascal, un outil pratique pour calculer les coefficients binomiaux.

Dans un contexte probabiliste, si l'on considère un arbre de décision avec n niveaux (succès-échec), le nombre de chemins comportant exactement k succès est égal à $\binom{n}{k}$. C'est une application concrète de ces coefficients.

La somme de tous les coefficients binomiaux d'une même ligne n du triangle de Pascal est égale à 2^n : $\sum_{k=0}^{n} \binom{n}{k} = 2^n$. Cette propriété montre le lien entre les combinaisons et le nombre total de parties d'un ensemble.

🔑 Le triangle de Pascal n'est pas qu'un simple outil de calcul, c'est une mine d'or mathématique ! Chaque nombre y est la somme des deux nombres situés au-dessus, ce qui facilite énormément les calculs de combinaisons.