Méthodes de dénombrement

Combinatoire et dénombrement — Terminale Spécialité

Méthodes de dénombrement

Introduction

Après avoir défini les outils fondamentaux de la combinatoire (permutations, arrangements, combinaisons), nous allons maintenant nous concentrer sur les méthodes qui permettent de résoudre efficacement les problèmes de dénombrement. Savoir choisir la bonne technique est la clé pour réussir ces exercices.

1. Rappel des principes fondamentaux

Principe additif (OU) : Si un choix peut se faire selon plusieurs cas mutuellement exclusifs, le nombre total de possibilités est la somme des possibilités de chaque cas :

[formule]

Principe multiplicatif (ET) : Si un choix se décompose en étapes successives indépendantes, le nombre total de possibilités est le produit des possibilités de chaque étape :

[formule]

Attention : bien distinguer OU et ET :

  • OU (cas exclusifs) → on additionne
  • ET (étapes successives) → on multiplie

Confondre les deux est l'erreur la plus fréquente en dénombrement !

Exemple : Un menu propose 3 entrées, 5 plats et 4 desserts. On choisit une entrée OU un dessert, puis un plat.

  • Choix entrée ou dessert : 3 + 4 = 7 (principe additif)
  • Avec le plat : 7 5 = 35 menus possibles (principe multiplicatif)

2. Tirages ordonnés

2.1 Tirages ordonnés avec répétition (p-listes)

p-liste (ou p-uplet) : Une p-liste d'un ensemble E à n éléments est une suite ordonnée de p éléments de E, avec répétition possible.

Le nombre de p-listes d'un ensemble à n éléments est :

[formule]

Quand utiliser n^p ? : On utilise cette formule quand :

  • L'ordre des éléments compte

  • La répétition est autorisée (on peut choisir plusieurs fois le même élément)

  • On effectue p choix parmi n possibilités à chaque étape

Exemple : codes et mots de passe : Code PIN à 4 chiffres (chiffres de 0 à 9, répétition autorisée) :

[formule]

Mot de passe de 6 caractères parmi 26 lettres minuscules :

[formule]

Exemple : plaques d'immatriculation : Une plaque est formée de 2 lettres (parmi 26), puis 3 chiffres (parmi 10), puis 2 lettres :

[formule]

2.2 Tirages ordonnés sans répétition (arrangements)

Arrangement : Un arrangement de k éléments parmi n (avec k n) est un choix ordonné de k éléments distincts parmi n.

[formule]

Quand utiliser les arrangements ? : On utilise les arrangements quand :

  • L'ordre des éléments compte

  • La répétition est interdite (chaque élément ne peut être choisi qu'une fois)

Exemple : podium : Dans une course de 12 athlètes, combien de podiums (or, argent, bronze) sont possibles ?

[formule]

L'ordre compte car les médailles sont distinctes, et un athlète ne peut pas occuper deux places.

Cas particulier : permutations : Quand k = n (on ordonne tous les éléments), l'arrangement devient une permutation :

[formule]

3. Tirages non ordonnés (combinaisons)

Combinaison : Une combinaison de k éléments parmi n est un choix de k éléments sans tenir compte de l'ordre.

[formule]

Quand utiliser les combinaisons ? : On utilise les combinaisons quand :

  • L'ordre ne compte pas (on forme un groupe, un sous-ensemble)

  • La répétition est interdite

Exemple : choix de délégués : De combien de façons peut-on choisir 4 délégués parmi 25 élèves ?

[formule]

Tableau récapitulatif :

Avec répétition Sans répétition
Ordonné p-listes : n^p Arrangements : A_n^k = n!{(n-k)!}
Non ordonné (hors programme) Combinaisons : n{k} = n!{k!(n-k)!}

4. Méthode du complémentaire

Dénombrement par le complémentaire : Pour dénombrer les cas satisfaisant « au moins un », il est souvent plus simple de compter le complémentaire :

[formule]

Cette technique est particulièrement utile quand le cas « aucun » est simple à calculer.

Exemple : au moins une fille : On forme un groupe de 5 personnes parmi 10 garçons et 8 filles. Combien de groupes contiennent au moins une fille ?

Total de groupes (sans contrainte) :

[formule]

Aucune fille (5 garçons parmi 10) :

[formule]

Au moins une fille :

[formule]

Exemple : mots de passe avec au moins un chiffre : Un mot de passe de 4 caractères est formé à partir de 26 lettres et 10 chiffres (36 caractères au total). Combien contiennent au moins un chiffre ?

Total : 36^4 = 1,679,616

Aucun chiffre (4 lettres) : 26^4 = 456,976

Au moins un chiffre : 1,679,616 - 456,976 = 1,222,640

Quand penser au complémentaire ? : Dès que vous voyez les mots :

  • « au moins un / une »
  • « pas tous identiques »
  • « au moins deux éléments différents »

Pensez immédiatement au complémentaire !

5. Diagramme en arbre

Organiser un dénombrement avec un arbre : Un diagramme en arbre permet de visualiser toutes les issues possibles d'une expérience à plusieurs étapes :

  1. Chaque nœud représente un choix

  2. Chaque branche représente une option possible

  3. Le nombre total d'issues = nombre de chemins de la racine aux feuilles

  4. Pour compter : on multiplie le long des branches, on additionne entre les branches

Exemple : choix de tenue : On dispose de 3 hauts (H₁, H₂, H₃) et 2 bas (B₁, B₂).

L'arbre a 3 branches au premier niveau (choix du haut), chacune se divisant en 2 branches (choix du bas).

Nombre total de tenues : 3 2 = 6.

Les 6 tenues sont : (H₁,B₁), (H₁,B₂), (H₂,B₁), (H₂,B₂), (H₃,B₁), (H₃,B₂).

Quand utiliser un arbre ? : L'arbre est particulièrement utile quand :

  • Le nombre de choix à chaque étape dépend des choix précédents
  • On veut lister toutes les possibilités (petits effectifs)
  • On combine des choix avec contraintes

6. Applications classiques

6.1 Codes et mots de passe

Exemple complet : mots de passe : Un mot de passe doit avoir exactement 8 caractères, composés de lettres majuscules (26) et de chiffres (10).

a) Nombre total de mots de passe (sans contrainte) :

[formule]

b) Nombre de mots de passe commençant par une lettre et finissant par un chiffre :

  • 1ère position : 26 choix (lettre)
  • Positions 2 à 7 : 36^6 choix chacune
  • 8ème position : 10 choix (chiffre)

[formule]

c) Nombre de mots de passe sans chiffre répété (mais lettres libres) :

Ce problème nécessite de distinguer les positions des chiffres et est plus complexe.

6.2 Mains de cartes

Jeu de 52 cartes : Un jeu standard contient 52 cartes :

  • 4 couleurs (♠, ♥, ♦, ♣)
  • 13 valeurs par couleur (As, 2, 3, ..., 10, Valet, Dame, Roi)

Exemple : mains de 5 cartes : Nombre total de mains de 5 cartes :

[formule]

Mains contenant exactement 2 As :

  • Choisir 2 As parmi 4 : 4{2} = 6
  • Choisir 3 cartes non-As parmi 48 : 48{3} = 17,296
  • Total : 6 17,296 = 103,776

Exemple : mains monochromes : Combien de mains de 5 cartes sont d'une même couleur (flush) ?

  • Choisir la couleur : 4{1} = 4
  • Choisir 5 cartes dans cette couleur : 13{5} = 1,287

[formule]

À retenir

Résumé :

  1. Tirages ordonnés avec répétition (p-listes) : n^p possibilités

  2. Tirages ordonnés sans répétition (arrangements) : A_n^k = n!{(n-k)!}

  3. Tirages non ordonnés sans répétition (combinaisons) : n{k} = n!{k!(n-k)!}

  4. Méthode du complémentaire : « au moins un » = total - « aucun »

  5. Diagramme en arbre : multiplier le long des branches, additionner entre les branches

  6. Questions clés pour choisir la bonne formule : l'ordre compte-t-il ? La répétition est-elle autorisée ?

  7. Applications courantes : codes, mots de passe, mains de cartes, formation de comités