Médaille
N°1 pour apprendre & réviser du collège au lycée.
Combinatoire et dénombrement

Déjà plus de

1 million

d'inscrits !

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, kk-uplet (ou kk-liste) ; produit cartésien de deux, trois, kk ensembles ; ensemble AkA^k des k-uplets d’éléments d’un ensemble AA.

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 kk-uplets (ou k-listes) d’un ensemble à nn éléments.
  • Nombre des parties d’un ensemble à nn éléments. Lien avec les nn-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 nn épreuves de Bernoulli.
  • Nombre des kk-uplets d’éléments distincts d’un ensemble à nn éléments. Définition de n ⁣n!. Nombre de permutations d’un ensemble fini à n éléments.
  • Combinaisons de kk éléments d’un ensemble à nn éléments : parties à kk éléments de l’ensemble. Représentation en termes de mots ou de chemins.
  • Pour 0kn0\leq k\leq n, (nk)=n(n1)...(nk+1)k ⁣=n ⁣(nk) ⁣k ⁣\dbinom n k =\dfrac{n(n-1)…(n-k+1)}{k!} =\dfrac{n!}{(n-k)!k!}
  • Explicitation pour k=0,1,2k=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 : k=0n(nk)=2n\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).