Combinatoire et dénombrement

Les ensembles considérés dans cette section sont finis mais on introduit dans le cas général (ensembles quelconques) les notions suivantes : couple, triplet, $k$-uplet (ou $k$-liste) ; produit cartésien de deux, trois, $k$ ensembles ; ensemble $A^k$ des k-uplets d’éléments d’un ensemble $A$.

Contenus

• Principe additif : nombre d’éléments d’une réunion d’ensembles deux à deux disjoints.
• Principe multiplicatif : nombre d’éléments d’un produit cartésien. Nombre de $k$-uplets (ou k-listes) d’un ensemble à $n$ éléments.
• Nombre des parties d’un ensemble à $n$ éléments. Lien avec les $n$-uplets de {0,1}, les mots de longueur n sur un alphabet à deux éléments, les chemins dans un arbre, les issues dans une succession de $n$ épreuves de Bernoulli.
• Nombre des $k$-uplets d’éléments distincts d’un ensemble à $n$ éléments. Définition de $n!$. Nombre de permutations d’un ensemble fini à n éléments.
• Combinaisons de $k$ éléments d’un ensemble à $n$ éléments : parties à $k$ éléments de l’ensemble. Représentation en termes de mots ou de chemins.
• Pour $0\leq k\leq n$, $\dbinom n k =\dfrac{n(n-1)…(n-k+1)}{k!} =\dfrac{n!}{(n-k)!k!}$
• Explicitation pour $k=0, 1, 2$. Symétrie. Relation et triangle de Pascal.

Capacités attendues

• Dans le cadre d’un problème de dénombrement, utiliser une représentation adaptée (ensembles, arbres, tableaux, diagrammes) et reconnaître les objets à dénombrer.
• Effectuer des dénombrements simples dans des situations issues de divers domaines scientifiques (informatique, génétique, théorie des jeux, probabilités, etc.).

Démonstrations

• Démonstration par dénombrement de la relation : $\textstyle\sum_{k=0}^n \dbinom{n}{k}=2^n$.
• Démonstrations de la relation de Pascal (par le calcul, par une méthode combinatoire).